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$