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.
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.
For each testcase print a single integer - the number of ways to choose the integer $k$.