N frogs are sitting in a single queue and are going to jump. Their jump is driven by some rules, as follows:
Given a permutation of [1, 2, ...N], lets say P.
Every second, all the frogs simultaneously move to new positions according to given P. The frog at position i, moves to position P[i].
Since P is a permutation, more than one frog are never at the same position.
Frogs are wearing a unique tag, that identifies their initial position.
When all the frogs are simultaneously back to their initial position, being tired they decide to take rest.
You are required to calculate the minimum number of seconds it will take such that all the frogs return to their initial order.

Input:

First line contains a integer T, the number of test cases.
Each test case consists of 2 lines. First line contains a single integer N, the number of frogs. Next line consists of N integers which defines the permutation P.

Output:

For each test case, output on a new line, the minimum number of seconds the frogs take to return to their initial order.

Constraints:
1 <= T <= 1000
1 <= N <= 1000

Sample Input
``` 2 3 3 2 1 11 4 11 9 6 7 1 2 5 3 8 10 ```
Sample Output
``` 2 6 ```

Problem Setter : Saurabh Vats
Problem Tester : Jayant Mukherji

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0