给定长度为$n(1 \le n \le 100000)$的正整数序列a，你需要构造一个长度为$n$的正整数序列$b$，使得对于所有的$i(1 \le i \le n)$,有1 <= $b_i$ <= $a_i$,且$gcd(b_1,b_2,...,b_n)$最大。试求出能得到的$gcd$最大值和取得最大值时，不同的数列 $b $的个数。由于答案可能很大，因此要对$998244353$取模。
定义两个长度为 $n$ 的数列 $c$,$d$ 不同，当且仅当存在整数$i(1 \le i \le n)$，使得 $c_i $ ≠ $d_i$。
注:$gcd$表示最大公约(因)数。比如 $gcd(2,4) = 2,gcd(3,4)=1,gcd(6,9,18) = 3, gcd(i,i,...,i) = i$ ($i \in N$)
第一行一个输入整数 $n$。($1 \le n \le 100000$)
第二行输入 $n$ 个整数，表示序列 $a$。($1 \le a_i \le 10^9$)
3
1 2 31 6