Some time ago Leonid have known about idempotent functions. Idempotent function defined on a set {1, 2, ..., n} is such function <image>, that for any <image> the formula g(g(x)) = g(x) holds.

Let's denote as f(k)(x) the function f applied k times to the value x. More formally, f(1)(x) = f(x), f(k)(x) = f(f(k - 1)(x)) for each k > 1.

You are given some function <image>. Your task is to find minimum positive integer k such that function f(k)(x) is idempotent.

Input

In the first line of the input there is a single integer n (1 ≤ n ≤ 200) — the size of function f domain.

In the second line follow f(1), f(2), ..., f(n) (1 ≤ f(i) ≤ n for each 1 ≤ i ≤ n), the values of a function.

Output

Output minimum k such that function f(k)(x) is idempotent.

Examples

Input

4
1 2 2 4


Output

1


Input

3
2 3 3


Output

2


Input

3
2 3 1


Output

3

Note

In the first sample test function f(x) = f(1)(x) is already idempotent since f(f(1)) = f(1) = 1, f(f(2)) = f(2) = 2, f(f(3)) = f(3) = 2, f(f(4)) = f(4) = 4.

In the second sample test: 

  * function f(x) = f(1)(x) isn't idempotent because f(f(1)) = 3 but f(1) = 2; 
  * function f(x) = f(2)(x) is idempotent since for any x it is true that f(2)(x) = 3, so it is also true that f(2)(f(2)(x)) = 3. 



In the third sample test: 

  * function f(x) = f(1)(x) isn't idempotent because f(f(1)) = 3 but f(1) = 2; 
  * function f(f(x)) = f(2)(x) isn't idempotent because f(2)(f(2)(1)) = 2 but f(2)(1) = 3; 
  * function f(f(f(x))) = f(3)(x) is idempotent since it is identity function: f(3)(x) = x for any <image> meaning that the formula f(3)(f(3)(x)) = f(3)(x) also holds.

Difficulty: HARD
Tags: Graph algorithms

Mathematics

Constructive algorithms

Starter code:

Solutions:
from random import randint
from copy import deepcopy
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= 1

def gen(n):
	a = []
	for i in range(n):
		a.append(randint(0, n - 1))
	return a

def stupid(a, v=False):
	n = len(a)
	init = [a[i] for i in range(n)]
	k = 1
	good = False
	while not good:
		good = True
		if v:
			print(a)
		for i in range(n):
			if a[a[i]] != a[i]:
				good = False
		if good:
			break
		k += 1
		b = [0 for i in range(n)]
		for i in range(n):
			b[i] = init[a[i]]
		a = [b[i] for i in range(n)]
	return k

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def get_lcm(a, b):
	return a * b // gcd(a, b)

def solve(a, v=False):
	n = len(a)
	d = [0 for i in range(n)]
	on_cycle = [False for i in range(n)]
	cycle_length = [0 for i in range(n)]
	until = [0 for i in range(n)]
	to_len = [0 for i in range(n)]
	for i in range(n):
		if a[i] == i:
			on_cycle[i] = True
			cycle_length[i] = 1
			continue
		cur = i
		cnt = 1
		for j in range(3 * n):
			cur = a[cur]
			cnt += cur == i
		on_cycle[i] = cnt > 1
		if on_cycle[i]:
			cur = i
			steps = 0
			for j in range(3 * n):
				cur = a[cur]
				steps += 1
				if cur == i:
					break
			cycle_length[i] = steps
	for i in range(n):
		if not on_cycle[i]:
			cur = i
			steps = 0
			for j in range(n + 1):
				cur = a[cur]
				steps += 1
				if on_cycle[cur]:
					break
			until[i] = steps
			to_len[i] = cycle_length[cur]
	if v:
		print('cycle', cycle_length)
		print('until', until)
	lcm = 1
	low = 0
	for i in range(n):
		if on_cycle[i]:
			lcm = get_lcm(lcm, cycle_length[i])
		else:
			low = max(low, until[i])
			continue
			to = to_len[i]
			p = until[i]
			if p % to:
				p = (p // to + 1) * to
			low = max(low, p)
			if v:
				print(i, p, to)
	ans = lcm
	while ans < low:
		ans += lcm
	return ans
print(solve(a))
while False:
	a = gen(randint(1, 15))
	print(a)
	print(stupid(deepcopy(a)))
	print(solve(deepcopy(a)))
	assert stupid(deepcopy(a)) == solve(deepcopy(a))


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
n = int(input())
v = [int(i) - 1 for i in input().split()]
b = [0] * n
r = 1
for i in range(n):
	(j, k) = (1, v[i])
	while j <= 2 * n + 10 and k != i:
		k = v[k]
		j += 1
	if k == i:
		r *= j // gcd(r, j)
		b[i] = 1
z = 0
for i in range(n):
	(j, k) = (0, i)
	while not b[k]:
		k = v[k]
		j += 1
	z = max(z, j)
j = z
if j > r:
	k = j // r
	if j % r != 0:
		k += 1
	r *= k
print(r)


def gcd(t1, t2):
	while t2 > 0:
		(t1, t2) = (t2, t1 % t2)
	return t1

def nok(t1, t2):
	return t1 * t2 // gcd(t1, t2)
n = int(input())
a = list(map(int, input().split()))
b = [0] * len(a)
c = []
d = [0]
cur = 0
while cur < len(a):
	b = [0] * len(a)
	pos = cur
	dis = 1
	while b[pos] >= 0:
		b[pos] = -dis
		pos = a[pos] - 1
		dis += 1
	c.append(dis + b[pos])
	d.append(-b[pos] - 1)
	cur += 1
r = 1
for x in c:
	r = nok(r, x)
up = max(d)
st = r
while r < up:
	r += st
print(r)


N = int(input())
inp = input().split()
F = [0 for i in range(N)]
for i in range(N):
	F[i] = int(inp[i]) - 1
ans_small = [0 for i in range(N + 1)]
for i in range(N):
	x = i
	y = i
	for j in range(N):
		x = F[x]
		y = F[F[y]]
		if x == y:
			ans_small[j + 1] += 1
ans = -1
for i in range(1, N + 1):
	if ans == -1:
		if ans_small[i] == N:
			ans = i
pw = [0 for i in range(500)]
for i in range(N):
	vis = [False for j in range(N)]
	vis[i] = True
	x = F[i]
	while vis[x] == False:
		vis[x] = True
		x = F[x]
	vis2 = [False for j in range(N)]
	vis2[x] = True
	x = F[x]
	while vis2[x] == False:
		vis2[x] = True
		x = F[x]
	c = 0
	for j in range(N):
		if vis2[j]:
			c += 1
	j = 2
	while j <= c:
		p = 0
		while c % j == 0:
			c //= j
			p += 1
		pw[j] = max(pw[j], p)
		j += 1
if ans == -1:
	ans = 1
	for i in range(1, 500):
		for j in range(pw[i]):
			ans *= i
	ans0 = ans
	while ans <= N:
		ans += ans0
print(ans)


from math import gcd
n = int(input())
f = list(map(int, input().split()))
vis = [0 for i in range(n)]
cyc = [False for i in range(n)]
dp = [0 for i in range(n)]

def dfs(u):
	if vis[u] == 2:
		return -1
	if vis[u] == 0:
		vis[u] = 1
		ret = dfs(f[u])
		vis[u] = 2
		return ret
	if vis[u] == 1:
		return u

def go(u):
	if dp[u] > 0:
		return dp[u]
	if cyc[u]:
		return 0
	dp[u] = go(f[u]) + 1
	return dp[u]
for i in range(n):
	f[i] -= 1
ans = 1
for i in range(n):
	u = dfs(i)
	if u == -1:
		continue
	cyc[u] = True
	v = f[u]
	w = 1
	while v != u:
		w += 1
		cyc[v] = True
		v = f[v]
	ans = ans * w // gcd(ans, w)
mx = 1
for i in range(n):
	if dp[i] == 0 and (not cyc[i]):
		mx = max(mx, go(i))
print((mx + ans - 1) // ans * ans)


import math

def ciclos(arr, i):
	de = {i: 0}
	cnt = 1
	while True:
		i = arr[i] - 1
		if i in de:
			return (de[i], cnt - de[i])
		de[i] = cnt
		cnt += 1

def mcm(a, b):
	return a * b // math.gcd(a, b)
n = int(input())
a = [int(x) for x in input().split()]
max_offset = -float('inf')
act_mcm = 1
aux_max = -float('inf')
for i in range(n):
	(off, lon) = ciclos(a, i)
	aux = lon if off == 0 else lon * math.ceil(off / lon)
	max_offset = max(max_offset, off)
	aux_max = max(aux_max, aux)
	act_mcm = mcm(act_mcm, lon)
print(act_mcm * math.ceil(aux_max / act_mcm))


n = int(input())
f = list(map(int, input().split()))

def proov(res):
	for i in range(len(f)):
		if res[i] != res[res[i]]:
			return False
	return True
for i in range(len(f)):
	f[i] -= 1

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
used = [0] * n
depth = [0] * n
on_circle = [False] * n

def dfs(s, d):
	ans = (0, float('inf'))
	used[s] = 1
	depth[s] = d + 1
	if used[f[s]] == 1:
		used[s] = 2
		ans = (depth[s] - depth[f[s]] + 1, depth[f[s]])
	if not used[f[s]]:
		ans = dfs(f[s], d + 1)
	if ans[1] <= depth[s]:
		on_circle[s] = True
	used[s] = 2
	return ans
res = list(range(n))
i = 0
circles = []
nok = 1
for i in range(n):
	if not used[i]:
		a = dfs(i, 0)
		if a[0] != 0:
			circles.append(a[0])
for i in range(len(circles)):
	nok = nok * circles[i] // gcd(nok, circles[i])
i = 0
while True:
	res = [f[res[j]] for j in range(n)]
	i += 1
	flag = True
	for j in range(n):
		flag = flag and on_circle[res[j]]
	if flag:
		print(max(nok, (i + nok - 1) // nok * nok))
		break
	if proov(res):
		print(i)
		break


from math import *
from random import *
from copy import *
import os
import sys
import fractions
n = int(input())
A = [0] + list(map(int, input().split()))
(X, Y) = (0, 1)
for i in range(1, n + 1):
	cnt = [-1] * (n + 1)
	now = i
	x = 0
	while cnt[now] == -1:
		cnt[now] = x
		now = A[now]
		x += 1
	y = x - cnt[now]
	x -= y
	X = max(X, x)
	Y = Y * y // fractions.gcd(Y, y)
print(max(Y, (X + Y - 1) // Y * Y))


import sys
import fractions
n = int(input())
refs = [0] * n
used = [0] * n
to = [int(x) - 1 for x in input().split(' ')]
for i in to:
	refs[i] += 1
times = []
max_a = 0
depth = [-1] * n

def dfs(u, d, depth):
	if depth[u] != -1:
		loop = d - depth[u]
		times.append(loop)
		global max_a
		if max_a < depth[u]:
			max_a = depth[u]
		return
	used[u] = True
	depth[u] = d
	return dfs(to[u], d + 1, depth)
for i in range(n):
	if refs[i] == 0:
		depth = [-1] * n
		b = dfs(i, 0, depth)
for i in range(n):
	if not used[i]:
		depth = [-1] * n
		b = dfs(i, 0, depth)
lcm = 1
for t in times:
	lcm = lcm * t // fractions.gcd(lcm, t)
ans = lcm
while ans < max_a:
	ans += lcm
print(ans)


n = int(input())
p = list(map(int, input().split()))
g = {}
deg = {}
first = []
circle = {}
ans = []

def push_d(deg, u, val):
	if u not in deg:
		deg[u] = 0
	deg[u] += val

def push_g(g, u, v):
	if u not in g:
		g[u] = []
	g[u].append(v)

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

def total(arr):
	cur = 1
	for x in arr:
		cur = cur // gcd(cur, x) * x
	return cur

def process(g, deg, deg0, u):
	if u in g:
		for v in g[u]:
			push_d(deg, v, -1)
			if deg[v] == 0:
				deg0.append(v)

def bfs(u):
	S = [u]
	used[u] = 1
	circle[u] = 1
	i = 0
	while i < len(S):
		u = S[i]
		if u in g:
			for v in g[u]:
				if used[v] == 0:
					used[v] = 1
					circle[v] = 1
					S.append(v)
		i += 1
	return len(S)

def bfs2(u):
	S = [u]
	start = 0
	i = 0
	while i < len(S):
		u = S[i]
		if u in g:
			for v in g[u]:
				if used[v] == -1:
					S.append(v)
				else:
					start = used[v]
		i += 1
	for u in S[::-1]:
		start += 1
		used[u] = start
	return start
for (u, v) in enumerate(p):
	u += 1
	push_d(deg, v, 1)
	push_g(g, u, v)
deg0 = [x for x in range(1, n + 1) if x not in deg]
first = [x for x in deg0]
used = [0 for x in range(n + 1)]
while len(deg0) > 0:
	u = deg0.pop()
	used[u] = 1
	process(g, deg, deg0, u)
cnt = []
for u in range(1, n + 1):
	if used[u] == 0:
		cnt.append(bfs(u))
used = [-1 for x in range(n + 1)]
for u in circle:
	used[u] = 0
max_ = 0
for u in first:
	max_ = max(max_, bfs2(u))
cur = total(cnt)
ans = cur
while ans < max_:
	ans += cur
print(ans)


import sys

def nod(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def nok(a, b):
	return a * b // nod(a, b)
n = int(input())
a = [0] + list(map(int, input().split()))
used = [False] * (n + 1)
ans = 1
for i in range(1, n + 1):
	t = i
	cnt = 0
	while 1:
		t = a[t]
		cnt += 1
		if t == i:
			ok = True
			break
		if cnt > n:
			ok = False
			break
	if ok:
		used[i] = True
		ans = nok(ans, cnt)
gl_ans = ans
for i in range(1, n + 1):
	if not used[i]:
		cnt = 0
		t = i
		while 1:
			if used[t]:
				break
			t = a[t]
			cnt += 1
		while gl_ans < cnt:
			gl_ans += ans
print(gl_ans)