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.
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.
For each test case, output on a new line, the minimum number of seconds the frogs take to return to their initial order.
1 <= T <= 1000
1 <= N <= 1000
3 2 1
4 11 9 6 7 1 2 5 3 8 10
Problem Setter : Saurabh Vats
Problem Tester : Jayant Mukherji