题目描述

Given a sequence $\boldsymbol{A} = (A_1, A_2, \ldots, A_N)$, a good subsequence of $\boldsymbol{A}$ is defined as a subsequence, that is not necessarily contiguous, where adjacent elements in the subsequence are not coprime.

Find the maximum length $L$ of a good subsequence of $\boldsymbol{A}$. Also, determine the number of good subsequences of length $L$, modulo $998,244,353$.

输入格式

The input is given in the following format:

$$\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$
• All input values are integers.

输出格式

Output 2 lines. On the first line, output $L$. On the second line, output the number of good subsequences of length $L$ of $\boldsymbol{A}$, modulo $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