给定一个序列 $a = (a_1, a_2, \dots, a_n)$。$a$ 的一个极好子序列是指一个子序列（不一定连续），其中相邻的元素不互质。

求 $a$ 的极好子序列的最大长度 $\ell$。此外，求长度为 $\ell$ 的极好子序列的数量，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)。

第二行包含序列 $a$，由 $n$ 个整数 $a_i$ ($1 \le a_i \le 10^6$) 组成。

输出格式

输出两行。

第一行输出 $\ell$。

第二行输出 $a$ 的长度为 $\ell$ 的极好子序列的数量，结果对 $998\,244\,353$ 取模。

样例

输入样例 1

3
2 3 6

输出样例 1

2
2

输入样例 2

5
1 1 1 1 1

输出样例 2

1
5

输入样例 3

10
631932 735902 895728 78537 723857 330739 286918 329211 539679 238506

输出样例 3

7
2