Yatin created an interesting problem for his college juniors. Can you solve it?

Given \(N\) rooms, where each room has a one-way door to a room denoted by \(room[i]\), where \(1 \leq i \leq N\). Find a positive integer \(K\) such that, if a person starts from room \(i\), \((1 <= i <= N)\) , and continuously moves to the room it is connected to (i.e. \(room[i]\)) , the person should end up in room \(i\) after \(K\) steps;

Note: The condition should hold for each room.If there are multiple possible values of \(K\) modulo (\(10^9 + 7\)), find the smallest one.If there is no valid value of K, output \(-1\)

Constraints:

\(1 \leq T \leq 10\)

\(1 \leq N \leq 10^5\)

\(1 \leq room[i] \leq N\)

Input Format

The first line of the input contains an integer \(T\), the number of testcases.
For each Testcase:
- The first line contains an integer \(N\), the number of rooms.
- The second line contains N spaced integers \(room[1], room[2]......room[N]\)

Output Format

Output the smallest positive integer \(K\) modulo \((10^9 +7)\) , satisfying the above-mentioned conditions.
If there is no such value, output \(-1\)