You are given a sequence of positive integers $a_1, a_2, \dots, a_n$. Determine how many intervals have a product that is a perfect square. That is, how many pairs $(l, r)$ ($1 \le l \le r \le n$) satisfy the condition that $\prod_{i=l}^r a_i$ is a perfect square.

Input

The first line contains an integer $n$, representing the number of elements. The next line contains $n$ integers, representing $a_1, a_2, \dots, a_n$.

Output

Output an integer representing the number of intervals whose product is a perfect square. Then, output these intervals in lexicographical order, i.e., sorted by $l$ in ascending order. If there are multiple intervals with the same $l$, sort them by $r$ in ascending order. If the number of such intervals exceeds $10^5$, output only the first $10^5$ of them.

Examples

Input 1

10
1 2 3 4 6 8 9 12 16 18

Output 1

12
1 1
1 5
2 5
3 6
3 7
4 4
4 8
4 9
5 8
5 9
7 7
9 9

Input 2

3
999999999999999956000000000000000363
999999999999999844000000000000004059
999999999999999866000000000000001353

Output 2

1
1 3

Note

In the second example, the product of the three numbers $10^{18} - 11$, $10^{18} - 33$, and $10^{18} - 123$ is a perfect square.

Examples 3, 4, 5

See the provided files square/square3.in and square/square3.ans, square/square4.in and square/square4.ans, and square/square5.in and square/square5.ans respectively.

Constraints

For all data, $1 \le n \le 3 \times 10^5$, $1 \le a_i \le 10^{36}$.