Read problems statements in Mandarin Chinese  and Russian. 
All bandits are afraid of Sheriff. Sheriff constantly fights crime, but when bandits lay low, he gets bored and starts to entertain himself. 
This time Sheriff gathered all the bandits in his garden and ordered them to line up. After the whistle all bandits should change the order in which they stand. 
Sheriff gave all the bandits numbers from 1 to N. For each place i he determined the unique position j. After whistling the bandit  staying on position i should run to the j-th position. Sheriff loved seeing how the bandits move around, and he continued whistling until the evening. He finished the game only when he noticed that the bandits are in the same order in which they were standing originally.
Now the Sheriff asks the question: How many times has he whistled?
 
------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of bandits. The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting that the bandit staying on position i should run to the A_{i}-th position after the whistle.
 
------ Output ------ 

For each test case, output a single line containing number of times the sheriff had to whistle, print it modulo 10^{9} + 7.
 
------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 100000$
$All A_{i} are distinct numbers from 1 to N$
 
----- Sample Input 1 ------ 
2
3
1 2 3
5
2 3 1 5 4
----- Sample Output 1 ------ 
1
6
----- explanation 1 ------ 
 
Example case 2.
the bandits positions are:
0. 1 2 3 4 5
1. 3 1 2 5 4
2. 2 3 1 4 5
3. 1 2 3 5 4
4. 3 1 2 4 5
5. 2 3 1 5 4
6. 1 2 3 4 5.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics


Solutions:
import fractions
test = int(input())
for i in range(test):
	n = int(input())
	array = [int(x) for x in input().split()]
	array.insert(0, 0)
	count = []
	seen = {}
	toSee = 0
	for i in range(1, n + 1):
		j = 1
		x = array[i]
		if x not in seen:
			seen[x] = None
			while x != i:
				x = array[x]
				seen[x] = None
				j += 1
			count.append(j)
			toSee += 1
	lcm = 1
	for i in range(toSee):
		lcm = lcm * count[i] // fractions.gcd(lcm, count[i])
	print(lcm % (10 ** 9 + 7))


from fractions import gcd
T = int(input())
for i in range(1, T + 1):
	N = int(input())
	l = [int(i) - 1 for i in input().split()]
	ls = [0] * N
	cycle = []
	for i in range(0, N):
		if ls[i] == 0:
			ls[i] = 1
			(c, d) = (l[i], 1)
			while c != i:
				ls[c] = 1
				c = l[c]
				d += 1
			cycle.append(d)
	lcm = 1
	for i in cycle:
		lcm = lcm * i // gcd(i, lcm)
	print(lcm % (10 ** 9 + 7))


from functools import reduce

def gcd(a, b):
	if b > a:
		return gcd(b, a)
	elif b == 0:
		return a
	else:
		return gcd(b, a % b)

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		shuffle = [0] + list(map(int, input().split()))
		visited = [False] * (n + 1)
		cycles = []
		for x in range(1, n + 1):
			if not visited[x]:
				cycle = 0
				while not visited[x]:
					cycle += 1
					visited[x] = True
					x = shuffle[x]
				cycles.append(cycle)
		print(reduce(lambda x, y: x * y // gcd(x, y), cycles) % 1000000007)
main()


def gcd(a, b):
	if b == 0:
		return a
	return int(gcd(b, a % b))

def fun(a, b):
	_gcd = gcd(a, b)
	product = a * b // _gcd
	return int(product)
T = int(input())
while T > 0:
	n = int(input())
	num = [0]
	vis = [0]
	x = input()
	for i in x.split():
		num.append(int(i))
		vis.append(0)
	div = []
	st = 1
	while st <= n:
		if vis[st] == 0:
			mark = st
			vis[st] = 1
			cnt = 1
			nx = num[st]
			while mark != nx:
				vis[nx] = 1
				nx = num[nx]
				cnt += 1
			if cnt not in div:
				div.append(cnt)
		st += 1
	ans = 1
	for each in div:
		ans = fun(ans, each)
	print(int(ans % 1000000007))
	T -= 1


import math

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
while t > 0:
	t = t - 1
	tot = 1
	n = int(input())
	position = input()
	pos = position.split(' ')
	b = []
	b = [False] * n
	for i in range(n):
		pos[i] = int(pos[i]) - 1
	for i in range(n):
		temp = 0
		if b[i] == True:
			continue
		init = pos[i]
		dup = init
		while True:
			temp = temp + 1
			dup = pos[dup]
			b[dup] = True
			if dup == init:
				break
		tot = lcm(tot, temp)
	print(int(tot % 1000000007))


def gcd(a, b):
	while b != 0:
		r = a % b
		a = b
		b = r
	return a
modulo = 1000000007
T = int(input())
arr = [None] * 100000
seen = [None] * 100000
step = [None] * 100000
while T > 0:
	T = T - 1
	N = int(input())
	for i in range(N):
		seen[i] = False
	arr[:] = map(int, input().split())
	s = 0
	for i in range(N):
		if seen[i]:
			continue
		count = 1
		index = arr[i]
		seen[index - 1] = True
		while index != i + 1:
			count = count + 1
			index = arr[index - 1]
			seen[index - 1] = True
		step[s] = count
		s = s + 1
	lcm = 1
	for i in range(s):
		lcm = lcm * step[i] // gcd(lcm, step[i])
	print(lcm % modulo)


import sys
from fractions import gcd
T = int(sys.stdin.readline())
C = 10 ** 9 + 7

def lcm(a, b):
	return a * b // gcd(a, b)
dicta = {}
for _ in range(T):
	N = int(sys.stdin.readline())
	lsta = [int(x) for x in sys.stdin.readline().split()]
	(out, i, elms, count, Counter, Low) = (-1, 0, 0, 1, 0, -1)
	while True:
		Low = i
		if lsta[i] != -1:
			elms += 1
			t = i
			Counter += 1
			i = lsta[i] - 1
			lsta[t] = -1
		else:
			if tuple([count, Counter]) in dicta:
				count = dicta[tuple([count, Counter])]
			else:
				x = lcm(count, Counter)
				dicta[tuple([count, Counter])] = x
				count = x
			if elms == N:
				break
			for k in range(Low, N):
				if lsta[k] != -1:
					i = k
					break
			Counter = 0
	if count < C:
		print(count)
	else:
		print(count % C)


from array import *
t = int(input())
while t > 0:
	ar = array('i', [0])
	br = array('i', [0])
	n = int(input())
	c = input()
	for i in c.split(' '):
		ar.append(int(i))
		br.append(0)
	j = 1
	lcm = 1
	while j <= n:
		count = 0
		while br[j] != 1:
			br[j] = 1
			j = ar[j]
			count = count + 1
		j = j + 1
		if count == 0:
			continue
		a = count
		b = lcm
		while b != 0:
			g = a % b
			a = b
			b = g
		lcm = count * lcm
		lcm = lcm // a
	print(lcm % 1000000007)
	t = t - 1


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
MOD = 10 ** 9 + 7
t = int(input())
while t > 0:
	t = t - 1
	w = 1
	n = int(input())
	A = [int(x) - 1 for x in input().split()]
	visited = [False] * n
	for i in range(n):
		if visited[i]:
			continue
		ans = 1
		pos = A[i]
		visited[i] = True
		while pos != i:
			visited[pos] = True
			ans = ans + 1
			pos = A[pos]
		w = lcm(w, ans)
	print(w % MOD)


from fractions import gcd
MOD = 10 ** 9 + 7

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
while t > 0:
	t -= 1
	ans = 1
	n = int(input())
	arr = list(map(int, input().split()))
	arr[:] = [x - 1 for x in arr]
	dups = n * [False]
	for i in range(n):
		cnt = 0
		if dups[i]:
			continue
		a = arr[i]
		b = a
		while 1:
			b = arr[b]
			dups[b] = True
			cnt += 1
			if a == b:
				break
		ans = lcm(ans, cnt)
	print(ans % MOD)


T = int(input())

def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 1
	s = set()
	for i in range(N):
		cnt = 0
		while i not in s:
			s.add(i)
			cnt += 1
			i = A[i] - 1
		if cnt > 0:
			ans = ans * cnt // gcd(ans, cnt)
	print(ans % 1000000007)


import math
mod = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	A = [int(x) - 1 for x in input().split()]
	if N == 1:
		print(1)
		continue
	lengths = []
	visited = [False] * N
	for i in range(N):
		if not visited[i]:
			j = i
			length = 0
			while not visited[j]:
				visited[j] = True
				j = A[j]
				length += 1
			lengths.append(length)
	lcm = 1
	for i in lengths:
		lcm = lcm * i // math.gcd(lcm, i)
	print(lcm % mod)


import fractions
import math

def gcd(a, b):
	return fractions.gcd(a, b)

def lcm(a, b):
	return a * b // gcd(a, b)
r = int(input(''))
for g in range(r):
	MOD = pow(10, 9) + 7
	x = int(input(''))
	y = input('').split(' ')
	y = [int(x) for x in y]
	dict = {}
	visited = {}
	for t in range(len(y)):
		dict[y[t]] = t + 1
	ans = 1
	for r in range(1, x + 1):
		if r not in visited:
			visited[r] = 1
			k = r
			xx = 0
			length = 0
			while k != r or xx == 0:
				xx = 1
				k = dict[k]
				visited[k] = 1
				length += 1
			ans = lcm(ans, length)
	print(int(ans % MOD))


from fractions import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	n = int(input())
	swap = [int(x) for x in input().split()]
	swap_dict = {i: True for i in range(1, n + 1)}
	lcm_set = set()
	for i in range(1, n + 1):
		if swap_dict[i]:
			cycle = 1
			nextt = swap[i - 1]
			while nextt != i:
				swap_dict[nextt] = False
				nextt = swap[nextt - 1]
				cycle += 1
			swap_dict[i] = False
			lcm_set.add(cycle)
	whistles = 1
	for i in lcm_set:
		whistles = lcm(i, whistles)
	mod = 10 ** 9 + 7
	print(whistles % mod)


def gcd(a, b):
	x = min(a, b)
	y = max(a, b)
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	lcm = x * y // gcd(x, y)
	return lcm

def main():
	t = int(input())
	for test in range(t):
		n = int(input())
		arr = list(map(int, input().split(' ')))
		for i in range(n):
			arr[i] -= 1
		done = [0] * n
		res = 1
		for i in range(n):
			if done[i] != 1:
				j = i
				done[j] = 1
				cycle = 1
				j = arr[j]
				while j != i:
					done[j] = 1
					cycle += 1
					j = arr[j]
			res = lcm(res, cycle)
		print(res % 1000000007)
main()


MOD = int(1000000000.0) + 7

def factorize(n: int, i: int) -> dict:
	p = 0
	while n % i == 0:
		p += 1
		n //= i
	return {i: p}

def fill_factors(n: int) -> list:
	factors = [{} for i in range(n + 1)]
	for i in range(2, n):
		if factors[i] == {}:
			for j in range(1, n // i + 1):
				factors[i * j].update(factorize(j * i, i))
	return factors
FACTORS = fill_factors(100000)

def mod_mul(a: list, mod: int) -> int:
	n = len(a)
	if n == 1:
		return a[0]
	return mod_mul(a[:n // 2], mod) * mod_mul(a[n // 2:], mod) % mod

def mod_power(a: int, p: int, mod: int) -> int:
	if a == 1 or p == 0:
		return 1
	if p == 1:
		return a
	m = mod_power(a, p // 2, mod)
	return mod_mul([m, m, mod_power(a, p % 2, mod)], mod)

def lcm(loops: list) -> int:
	n = len(loops)
	if n == 0:
		return 1
	if n == 1:
		return loops[0]
	primes = {}
	for loop in loops:
		for (prime, power) in FACTORS[loop].items():
			if prime not in primes:
				primes[prime] = power
			else:
				primes[prime] = max(primes[prime], power)
	return mod_mul([mod_power(prime, power, MOD) for (prime, power) in primes.items()], MOD)

def get_loops(n: int, a: list) -> list:
	covered = [0] * n
	loops = []
	for i in range(n):
		if covered[i] == 0:
			(st, end) = (i, i)
			loop = 0
			while True:
				loop += 1
				end = a[end]
				covered[end] = 1
				if st == end:
					break
			if loop > 1:
				loops.append(loop)
	return loops

def solve(n: int, a: list) -> int:
	loops = get_loops(n, a)
	return lcm(loops)
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = [int(i) - 1 for i in input().strip().split()]
	print(solve(n, a))


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def solve(vals):
	ans = 1
	for v in vals:
		ans = lcm(ans, v)
	return ans % (10 ** 9 + 7)
T = int(input())
for i in range(T):
	input()
	arr = [int(x) - 1 for x in input().rstrip().split(' ')]
	vis = [0] * len(arr)
	vals = []
	for j in range(len(arr)):
		cnt = 0
		t = j
		while vis[t] != 1:
			cnt += 1
			vis[t] = 1
			t = arr[t]
		if cnt > 1:
			vals.append(cnt)
	print(solve(vals))


def find_set(x):
	if fa[x] != x:
		fa[x] = find_set(fa[x])
	return fa[x]

def gcd(x, y):
	if x == 0:
		return y
	return gcd(y % x, x)

def lcm(x, y):
	return x * y // gcd(x, y)
fa = [0 for i in range(100001)]
ncase = int(input())
while ncase > 0:
	ncase -= 1
	n = int(input())
	a = input().split(' ')
	for i in range(n):
		fa[i + 1] = i + 1
	for i in range(n):
		x = int(a[i])
		fx = find_set(x)
		fy = find_set(i + 1)
		if fx != fy:
			fa[fx] = fy
	sz = [0 for i in range(n + 1)]
	for i in range(n):
		sz[find_set(i + 1)] += 1
	ans = 1
	for i in range(n):
		if sz[i + 1] > 1:
			ans = lcm(ans, sz[i + 1])
	print(ans % 1000000007)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * (b // gcd(a, b))
mod = 1000000007
T = int(input())
for i in range(T):
	N = int(input())
	v = input().split()
	for j in range(len(v)):
		v[j] = int(v[j])
	used = [False for j in range(N)]
	ans = 1
	for j in range(N):
		if used[j] == False:
			times = 1
			current = v[j]
			used[j] = True
			while current - 1 != j:
				used[current - 1] = True
				current = v[current - 1]
				times += 1
			ans = lcm(ans, times)
	print(ans % mod)


import fractions
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = []
	v = []
	nm = []
	tm = input().split()
	for i in range(n):
		a.append(int(tm[i]))
		a[i] -= 1
		v.append(False)
	for i in range(n):
		cm = int(1)
		if v[i] == False:
			k = a[i]
			v[i] = True
			while k != i:
				v[k] = True
				k = a[k]
				cm = cm + 1
		if cm > 1:
			nm.append(int(cm))
	if len(nm) < 1:
		ansr = 1
	else:
		ansr = int(nm[0])
	for i in range(1, len(nm)):
		ansr = ansr * int(nm[i]) // int(fractions.gcd(ansr, nm[i]))
	ansr = int(ansr)
	ansr = ansr % 1000000007
	print(ansr)


def hcf(a, b):
	if a % b == 0:
		return b
	else:
		return hcf(b, a % b)

def lcm(a, b):
	return a * b // hcf(a, b)
MOD = 10 ** 9 + 7
t = int(input())
while t > 0:
	n = int(input())
	arr = [0] * (n + 1)
	visited = [False] * (n + 1)
	temp = input().split(' ')
	for i in range(1, n + 1):
		arr[i] = int(temp[i - 1])
	allCounts = []
	for i in range(1, n + 1):
		if visited[i] == False:
			j = i
			count = 0
			while visited[j] == False:
				visited[j] = True
				j = arr[j]
				count += 1
			allCounts.append(count)
	ans = allCounts[0]
	for i in range(1, len(allCounts)):
		ans = lcm(ans, allCounts[i])
	print(ans % MOD)
	t -= 1