There are **N** monkeys in a circus. They dance in a circular formation, very similar to a Gujarati Garba or a Drum Circle. The dance requires the monkeys to constantly change positions after every **1 second**. The change of position is not random & you, in the audience, observe a pattern. Monkeys are very disciplined & follow a specific pattern while dancing.

Consider N = **6**, and the dancing pattern of the 6 monkeys = **{3,6,5,4,1,2}**.

The value at **monkeys[i]**, indicates the new position of the monkey who is standing at the i^{th} position.

The program must accept N integers representing the dancing pattern of the monkeys. The program must print the time after which all the monkeys are in the initial position for the first time.

__Note:__ Optimize your logic to avoid Time Limit Exceed error.

**Boundary Condition(s):**

1 <= T <= 10

1 <= N <= 10000

**Input Format:**

The first line contains T which represents the number of test cases.

Each test case consists of the following.

The first line contains N denoting the number of monkeys.

The next line contains N integers denoting the dancing pattern array.

**Output Format:**

The first T lines, each contains an integer representing the minimum number of seconds after which all the monkeys are in their initial position.

**Example Input/Output 1:**

Input:

1

6

4 3 1 5 6 2

Output:

6

Explanation:

In the first test case, N = **6** and the dancing pattern = **{4,3,1,5,6,2}**.

Suppose monkeys are a,b,c,d,e,f & Initial position (at t = 0) -> **a,b,c,d,e,f**

At t = **1** -> **c,f,b,a,d,e****a** will move to 4^{th} position, **b** will move to 3^{rd} position, **c** will move to 1^{st} position, **d** will move to 5^{t}h position, **e** will move to 6^{th} position and **f** will move to 2^{nd} position.

Recursively applying the same transpositions, we get the following positions for different values of t.

At t = **2** -> **b,e,f,c,a,d**

At t = **3** -> **f,d,e,b,c,a**

At t = **4** -> **e,a,d,f,b,c**

At t = **5** -> **d,c,a,e,f,b**

At t = **6** -> **a,b,c,d,e,f**

Since at **t = 6**, we got the original position, hence the output is 6.

**Example Input/Output 2:**

Input:

3

10

3 6 5 7 10 4 2 8 1 9

4

4 3 2 1

7

3 6 1 4 7 5 2

Output:

20

2

4

```
from math import gcd
def l(x,y):
return(int((x*y)/gcd(x,y)))
n=int(input())
while(n):
n=n-1
a=int(input())
m=list(map(int,input().split()))
t=1;c=0;p=0
while(p<=a-1):
b=p;c=0
while(m[p]!=0):
h=p
p=m[p]-1
m[h]=0
c+=1
p=b+1
if(c!=0):
t=l(t,c)
print(int(t))
```