Description

你知道什么是“互质序列”吗？那就是所有数的最大公约数恰好为1的序列。

“互质序列”非常容易找到，但是我们可以尝试通过删除这个序列的一个非空连续子序列来扩大它的最大公约数。

现在给定一个长度为n的序列，你需要从中删除一个非空连续子序列，使得剩下至少2个数，令E为剩下数的最大公约数的期望值，S为合法的方案数，请计算E*S的值。因为这个值可能非常大，请对998244353取模输出。

Format

Input

第一行包含一个正整数n(3<=n<=100000)，表示序列的长度。

第二行包含n个正整数a_1,a_2,...,a_n(1<=a_i<=10^9)，分别表示序列中的每个元素。

Output

输出一行一个整数，即E*S mod 998244353的值。

Samples

5
3 4 5 2 9

14