A set of numbers is called brotherly if there exists a number $p > 1$ such that $p$ divides all numbers in that set. Mr. Malnar received a permutation $P$ of numbers from $1$ to $n$ as a gift, which is a bit too long, so he will keep only the first few numbers of it.

Since Mr. Malnar loves brotherly sets, he is interested in how many non-empty brotherly subsets each prefix of the permutation $P$ contains. We all know that Mr. Malnar has more important work to do than counting subsets, so he has asked you to help him. Because these numbers are too large, he is only interested in the result modulo $998\,244\,353$.

Input

The first line contains a natural number $n$ ($1 \le n \le 3 \cdot 10^5$).

The next line contains $n$ numbers, where the $i$-th number is $P_i$, i.e., the $i$-th number of the permutation $P$.

Output

You need to print $n$ lines. In the $i$-th line, you need to print the remainder of the number of brotherly subsets in the prefix of length $i$ when divided by $998\,244\,353$.

Examples

Input 1

5
2 3 1 4 5

Output 1

1
2
2
4
5

Input 2

6
1 5 6 2 3 4

Output 2

0
1
2
4
6
10