There are N frogs Near a Pond. Consider that initially positions(at t = 0) of the frogs are numbered from 0 to N-1. They all started playing a game. In this game the frogs exchange their positions between each others. Positions are exchanged using the following rule
- Each frog when at a position i will always make a jump to position j.
Considering that all the frog jumps takes simultaneously and takes one unit of time, then find out the minimum time after which all the frogs will be at their starting positions.
Input format:
Input begins with an integer T, no of test cases, Each test case has two lines. First Line contains a number N(No of frogs). second line contains N space separated integers, ith such integer denotes the position j where the frog will make jump to when at position i.
Output format:
For each testcase output a single line containing the minimum time t after which all the frogs return to their initial position.
Example:
Input:
2
8
0 1 2 3 4 5 6 7
8
1 3 4 0 6 5 2 7
Output:
1
3
Input Limit:
1 <= T <= 10000
1 <= N <= 200
Notes: Input will be such that no 2 frogs will jump to same position at the same time.
Explanation:
for first testcase each frog is jumping at its own position so after 1 unit of time from t = 0 they all will be at their starting position for the first time.
