说明

给定一个序列 $\boldsymbol{A} = (A_1, A_2, \ldots, A_N)$，定义 $\boldsymbol{A}$ 的一个好子序列为这样一个子序列（不要求连续），其中子序列内相邻的两个元素不互质。

求 $\boldsymbol{A}$ 的好子序列的最大可能长度 $L$。同时，求出长度为 $L$ 的好子序列的数量，结果对 $998,244,353$ 取模。

输入格式

输入以如下格式给出：

$$\begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_N \end{aligned}$$

• $1 \leq N \leq 200,000$
• $1 \leq A_i \leq 10^6$
• 所有输入值均为整数。

输出格式

输出两行。第一行输出 $L$。第二行输出 $\boldsymbol{A}$ 中长度为 $L$ 的好子序列的数量，结果对 $998,244,353$ 取模。

3
2 3 6

2
2

5
1 1 1 1 1

1
5

10
631932 735902 895728 78537 723857 330739 286918 329211 539679 238506

7
2

提示

翻译由 DeepSeek V3.2 完成