Question for the Leader

Problem Description

JRY is the leader of a village. He has $n$ lands, and there are $n$ roads connecting them. There is at most one road connecting two lands and all lands are connected. Now, JRY wants to divided the $n$ lands into $k$ disjoint sets of equal size, satisfying that one can move between any two lands belonging to the same set passing only through lands frome this set. Furthermore, he wants to know how many $k(1\leq k\leq n)$ he can choose.

Input

There are multiple testcases, the sum of $n$ is less then $10^6$. For each test case, the first line contains one integer $n(1\leq n\leq 10^5)$. The next line contains $n$ integers, the $i$-th integer $a_i$ means that there is an edge between $i$ and $a_i$. It is guaranteed that the graph doesn't contain self loops and multiple edges.

Output

For each testcase print a single integer - the number of ways to choose the integer $k$.

Sample Input

6
2 3 4 5 6 1
6
2 4 2 3 4 3

Sample Output

4
3

Hint

Case 1 : $k$ = 1,2,3,6 Case 2: $k$ = 1,3,6

Author

XJZX

Source

2015 Multi-University Training Contest 4