Polycarp found the string $s$ and the permutation $p$. Their lengths turned out to be the same and equal to $n$.

A permutation of $n$ elements — is an array of length $n$, in which every integer from $1$ to $n$ occurs exactly once. For example, $[1, 2, 3]$ and $[4, 3, 5, 1, 2]$ are permutations, but $[1, 2, 4]$, $[4, 3, 2, 1, 2]$ and $[0, 1, 2]$ are not.

In one operation he can multiply $s$ by $p$, so he replaces $s$ with string $new$, in which for any $i$ from $1$ to $n$ it is true that $new_i = s_{p_i}$. For example, with $s=wmbe$ and $p = [3, 1, 4, 2]$, after operation the string will turn to $s=s_3 s_1 s_4 s_2=bwem$.

Polycarp wondered after how many operations the string would become equal to its initial value for the first time. Since it may take too long, he asks for your help in this matter.

It can be proved that the required number of operations always exists. It can be very large, so use a 64-bit integer type.


-----Input-----

The first line of input contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases in input.

The first line of each case contains single integer $n$ ($1 \le n \le 200$) — the length of string and permutation.

The second line of each case contains a string $s$ of length $n$, containing lowercase Latin letters.

The third line of each case contains $n$ integers — permutation $p$ ($1 \le p_i \le n$), all $p_i$ are different.


-----Output-----

Output $t$ lines, each of which contains the answer to the corresponding test case of input. As an answer output single integer — the minimum number of operations, after which the string $s$ will become the same as it was before operations.


-----Examples-----

Input
3
5
ababa
3 4 5 2 1
5
ababa
2 1 4 5 3
10
codeforces
8 6 1 7 5 2 9 3 10 4
Output
1
6
12


-----Note-----

In the first sample operation doesn't change the string, so it will become the same as it was after $1$ operations.

In the second sample the string will change as follows:

$s$ = babaa

$s$ = abaab

$s$ = baaba

$s$ = abbaa

$s$ = baaab

$s$ = ababa

Difficulty: MEDIUM_HARD
Tags: Number theory

Graph algorithms

Mathematics

String algorithms

Starter code:

Solutions:
import math

def shift(s) -> int:
	for i in range(1, len(s)):
		if s == s[i:] + s[:i]:
			return i
	return len(s)

def solve():
	n = int(input())
	s = input()
	p = [int(x) - 1 for x in input().split()]
	vis = [False] * n
	ans = 1
	for i in range(n):
		if vis[i]:
			continue
		ss = ''
		j = i
		ss += s[j]
		vis[j] = True
		j = p[j]
		while j != i:
			ss += s[j]
			vis[j] = True
			j = p[j]
		ln = shift(ss)
		ans = ans * ln // math.gcd(ans, ln)
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from math import gcd

def solve():
	n = int(input())
	s = input()
	p = list(map(int, input().split()))
	v = [False for _ in p]
	lcm = 1
	for per in p:
		if v[per - 1]:
			continue
		v[per - 1] = True
		str_bef = s[per - 1]
		pos = p[per - 1] - 1
		while not v[pos]:
			str_bef += s[pos]
			v[pos] = True
			pos = p[pos] - 1
		str_after = str_bef
		num = 1
		str_after = shift_chars(str_after)
		while str_bef != str_after:
			str_after = shift_chars(str_after)
			num += 1
		lcm = lcm * num // gcd(lcm, num)
	return lcm

def shift_chars(string):
	return string[-1] + string[:-1]
tt = int(input())
for _ in range(tt):
	print(solve())


from math import gcd
I = lambda : int(input())
Is = lambda : map(int, input().split())
Li = lambda : list(map(int, input().split()))

def solve():
	n = I()
	s = input()
	a = Li()
	dic = {}
	path = []
	seen = set()
	lst = []
	for (index, i) in enumerate(a):
		dic[i] = index + 1
	for i in a:
		if i not in seen:
			tmp = s[i - 1]
			cur = i
			head = cur
			seen.add(i)
			while dic[cur] != head:
				cur = dic[cur]
				tmp += s[cur - 1]
				seen.add(cur)
			path.append(tmp)
	for i in path:
		tmp = i
		i = i[-1] + i[:-1]
		t = 1
		while i != tmp:
			i = i[-1] + i[:-1]
			t += 1
		lst.append(t)
	ans = lst[0]
	for i in lst[1:]:
		ans = ans * i // gcd(ans, i)
	print(ans)
	return 1
t = I()
while t:
	solve()
	t -= 1


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

def shift(s):
	for i in range(1, len(s) + 1):
		if s == s[i:] + s[:i]:
			return i

def solve():
	n = int(input())
	s = input()
	p = [int(x) - 1 for x in input().split()]
	used = [False] * n
	ans = 1
	i = 0
	while i < n:
		ss = ''
		while not used[i]:
			ss += s[i]
			used[i] = True
			i = p[i]
		i += 1
		if len(ss) == 0:
			continue
		ln = shift(ss)
		ans = ans * ln // gcd(ans, ln)
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline
from math import gcd
for _ in range(int(input())):
	n = int(input())
	s = input()[:-1]
	w = list(map(int, input().split()))
	d = [0] * n
	ans = 1
	for i in range(n):
		if not d[i]:
			d[i] = 1
			a = i
			p = s[i]
			while 1:
				a = w[a] - 1
				if d[a] == 1:
					break
				d[a] = 1
				p += s[a]
			m = p
			c = 0
			while 1:
				m = m[1:] + m[0]
				c += 1
				if m == p:
					break
			ans = ans * c // gcd(ans, c)
	print(ans)


from math import gcd

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

def helper(a):
	ans = len(a)
	for i in range(1, len(a) // 2 + 1):
		q = len(a) // i
		if a[:i] * q == a:
			return i
	return ans
for _ in range(int(input())):
	n = int(input())
	s = input()
	arr = list(map(int, input().split()))
	ch = []
	seen = set()
	res = []
	for i in range(n):
		temp = []
		if i not in seen:
			while i not in seen:
				temp.append(s[i])
				seen.add(i)
				i = arr[i] - 1
			res.append(helper(''.join(temp)))
	start = res[0]
	for el in res[1:]:
		start = lcm(start, el)
	print(start)


import math
x = int(input())

def cal(n, s, arr):
	dic = {}
	for (i, v) in enumerate(arr):
		dic[v] = i
	gr = []
	for i in range(n):
		if i not in dic:
			continue
		j = i
		p = []
		while j in dic:
			p.append(j)
			a = j
			j = dic[a]
			del dic[a]
		gr.append(p)
	res = []
	for i in gr:
		st = ''
		for j in i:
			st += s[j]
		k = len(st)
		for j in range(1, k + 1):
			if st[j % k:] + st[:j % k] == st:
				res.append(j)
				break
	ans = 1
	for i in res:
		ans = ans * i // math.gcd(ans, i)
	return ans
for jj in range(x):
	n = int(input())
	s = input()
	arr = [int(i) - 1 for i in input().split(' ')]
	print(cal(n, s, arr))


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

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

def shift(s):
	for i in range(1, len(s) + 1):
		if s[i:] + s[:i] == s:
			return i

def sol():
	n = int(input())
	s = input()
	p = [int(x) - 1 for x in input().split()]
	i = 0
	vis = [False] * n
	ans = 1
	while i < n:
		x = i
		st = ''
		while not vis[x]:
			st += s[x]
			vis[x] = 1
			x = p[x]
		i += 1
		if len(st) == 0:
			continue
		now = shift(st)
		ans = lcm(ans, now)
	print(ans)
t = int(input())
while t:
	t -= 1
	sol()


import abc
import itertools
import math
from math import gcd as gcd
import sys
import queue
import itertools
from heapq import heappop, heappush
import random

def solve():

	def psevdo_dfs(s, c):
		l = ''
		while p[c] != 0:
			l += s[p[c] - 1]
			tmp = c * 1
			c = p[c] - 1
			p[tmp] = 0
		return l
	n = int(input())
	s = str(input())
	p = list(map(int, input().split()))
	r = []
	for i in range(n):
		if p[i] != 0:
			l = psevdo_dfs(s, i)
			w = l[-1] + l[0:len(l) - 1]
			q = 1
			for j in range(len(l)):
				if w == l:
					break
				else:
					q += 1
					w = w[-1] + w[0:len(w) - 1]
			r.append(q)
	for i in range(1, len(r)):
		r[i] = r[i - 1] * r[i] // math.gcd(r[i - 1], r[i])
	print(r[-1])
multi_test = 1
if multi_test == 1:
	t = int(sys.stdin.readline())
	for _ in range(t):
		solve()
else:
	solve()


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

def rotations(t):
	for i in range(1, len(t) + 1):
		if t == t[i:] + t[:i]:
			return i
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = [int(i) - 1 for i in input().split()]
	visited = [False] * n
	ans = 1
	for i in range(n):
		if visited[i]:
			continue
		visited[i] = True
		j = p[i]
		t = s[i]
		while j != i:
			t += s[j]
			visited[j] = True
			j = p[j]
		rotation = rotations(t)
		ans = ans * rotation // gcd(ans, rotation)
	print(ans)


def findRotations(str):
	tmp = str + str
	n = len(str)
	for i in range(1, n + 1):
		substring = tmp[i:i + n]
		if str == substring:
			return i
	return n

def calculate_lcm(num1, num2):
	if num1 > num2:
		num = num1
		den = num2
	else:
		num = num2
		den = num1
	rem = num % den
	while rem != 0:
		num = den
		den = rem
		rem = num % den
	gcd = den
	lcm = int(int(num1 * num2) / int(gcd))
	return lcm

def solve(n, s, array):
	done = [False for i in range(n)]
	cycles = []
	for i in range(n):
		if not done[i]:
			start = i
			newS = []
			j = i + 1
			while array[j - 1] - 1 != start:
				newS += s[j - 1]
				done[j - 1] = True
				j = array[j - 1]
			newS.append(s[j - 1])
			done[j - 1] = True
			cycles.append(''.join(newS))
	ans = []
	for i in cycles:
		ans.append(findRotations(i))
	result = ans[0]
	for i in range(1, len(ans)):
		result = calculate_lcm(result, ans[i])
	return result
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	array = [int(i) for i in input().split(' ')]
	print(solve(n, s, array))


import math
tc = int(input())
for t in range(tc):
	n = int(input())
	s = input()
	arr = list(map(int, input().split()))
	num = []
	vis = set()
	ans = 1
	for i in range(n):
		if i not in vis:
			j = arr[i] - 1
			vis.add(i)
			coun = 0
			ch = s[i]
			while j != i:
				vis.add(j)
				ch = ch + s[j]
				j = arr[j] - 1
			l = ch
			while 1:
				l = l[1:] + l[0]
				coun = coun + 1
				if l == ch:
					break
			ans = ans * coun // math.gcd(ans, coun)
	print(ans)


import math
import sys
input = sys.stdin.readline
from collections import defaultdict as dd
T = int(input())
for _ in range(T):
	n = int(input())
	s = input().strip()
	ll = list(map(int, input().split()))
	gr = dd(set)
	for i in range(n):
		ll[i] -= 1
	vis = [0] * n
	lt = []
	for i in range(n):
		if vis[i] == 0:
			ss = s[i]
			j = ll[i]
			vis[i] = 1
			while vis[j] != 1:
				ss += s[j]
				vis[j] = 1
				j = ll[j]
			lt.append(ss)
	nt = []
	for each in lt:
		here = each[1:] + each[0]
		go = 1
		while each != here:
			here = here[1:] + here[0]
			go += 1
		nt.append(go)
	ans = nt[0]
	for it in nt[1:]:
		ans = ans * it // math.gcd(ans, it)
	print(ans)


from sys import stdin
from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
for test in range(int(input())):
	n = int(input())
	string = input().strip()
	seq = [0] + list(map(int, input().split()))
	check = [0] + [1] * n
	l = 1
	for i in range(1, n + 1):
		if check[i]:
			cycle = [i, seq[i]]
			check[cycle[-1]] = 0
			while cycle[-1] != i:
				cycle.append(seq[cycle[-1]])
				check[cycle[-1]] = 0
			cycle.pop()
			str_check = ''.join((string[s - 1] for s in cycle))
			x = 1
			while str_check[x:] + str_check[:x] != str_check:
				x += 1
			l = lcm(l, x)
	print(l)


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = [int(x) for x in input().split()]
	num = []
	vis = set()
	ans = 1
	for i in range(n):
		if i not in vis:
			j = p[i] - 1
			vis.add(i)
			count = 0
			ch = s[i]
			while j != i:
				vis.add(j)
				ch = ch + s[j]
				j = p[j] - 1
			l = ch
			while l:
				l = l[1:] + l[0]
				count = count + 1
				if l == ch:
					break
			ans = ans * count // math.gcd(ans, count)
	print(ans)


import math, sys, bisect, collections

def shift(s):
	for i in range(1, len(s) + 1):
		if s == s[i:] + s[:i]:
			return i
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = [int(x) - 1 for x in input().split()]
	(used, ans, i) = ([False] * n, 1, 0)
	while i < n:
		ss = ''
		while not used[i]:
			ss = ss + s[i]
			used[i] = True
			i = p[i]
		i += 1
		if len(ss) == 0:
			continue
		ln = shift(ss)
		ans = ans * ln // math.gcd(ln, ans)
	print(ans)


import math

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def repeat(string):
	n = len(string)
	for rot in range(n):
		if string == string[n - 1 - rot:] + string[:n - 1 - rot]:
			return rot + 1
for _ in range(int(input())):
	(n, s, p) = (int(input()), input(), list(map(lambda x: int(x) - 1, input().split())))
	v = [False] * n
	cstr = []
	for i in range(n):
		cs = ''
		if v[i]:
			continue
		while True:
			cs += s[i]
			(v[i], i) = (True, p[i])
			if v[i]:
				break
		cstr.append(cs)
	r = 1
	for i in range(len(cstr)):
		r = lcm(r, repeat(cstr[i]))
	print(r)


import math
x = int(input())
for t in range(x):
	k = int(input())
	s = input()
	arr = [int(i) - 1 for i in input().split()]
	visited = [False] * k
	y = []
	for i in arr:
		l = []
		ss = ''
		u = i
		while not visited[u]:
			ss += s[u]
			visited[u] = True
			u = arr[u]
		if ss:
			y += [ss]
	for (ii, i) in enumerate(y):
		ss = i
		for j in range(len(ss)):
			ss = ss[1:] + ss[0]
			if ss == i:
				y[ii] = j + 1
				break
	mb = 1
	for i in y:
		mb = i * mb // math.gcd(mb, i)
	print(mb)


import math
l = lambda : map(lambda x: int(x) - 1, input().split())

def f(s):
	for i in range(1, len(s) + 1):
		if s == s[i:] + s[:i]:
			return i
for t in range(int(input())):
	n = int(input())
	s = input()
	p = [*l()]
	v = [True] * n
	(z, i) = (1, 0)
	while i < n:
		w = ''
		while v[i]:
			w += s[i]
			v[i] = False
			i = p[i]
		i += 1
		if len(w) == 0:
			continue
		r = f(w)
		z *= r // math.gcd(z, r)
	print(z)


from math import gcd

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

def count(str):
	cnt = 1
	tmp = str[-1] + str[:len(str) - 1]
	while tmp != str:
		cnt += 1
		tmp = tmp[-1] + tmp[:len(tmp) - 1]
	return cnt
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	arr = list(map(int, input().split()))
	seen = {}
	cy = []
	for i in range(n):
		if i in seen:
			continue
		tmp = [i]
		cur = i
		seen[i] = 1
		while arr[cur] - 1 != i:
			cur = arr[cur] - 1
			seen[cur] = 1
			tmp.append(cur)
		cy.append(tmp)
	for i in range(len(cy)):
		for j in range(len(cy[i])):
			cy[i][j] = s[cy[i][j]]
	for i in range(len(cy)):
		cy[i] = ''.join(cy[i])
	ans = 1
	for i in range(len(cy)):
		ans = lcm(ans, count(cy[i]))
	print(ans)


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

def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	bl = [False for i in range(n)]
	s = input()
	l_for_gcd = []
	perm = [int(i) - 1 for i in input().split()]
	l = perm[0]
	for i in range(n):
		l = perm[i]
		if bl[i] == False:
			bl[i] = True
			strpart = s[i]
			j = perm[i]
			while perm[j] != l:
				bl[j] = True
				strpart += s[j]
				j = perm[j]
			counter = 0
			ns = strpart
			for k in range(len(strpart)):
				ns = ns[1:] + ns[0]
				counter += 1
				if ns == strpart:
					break
			l_for_gcd.append(counter)
	if len(l_for_gcd) == 1:
		print(int(l_for_gcd[0]))
	else:
		ans = l_for_gcd[0]
		for i in range(1, len(l_for_gcd)):
			ans = lcm(ans, l_for_gcd[i])
		print(int(ans))


def solve():
	n = int(input())
	s = input()
	p = list(map(int, input().split()))
	for i in range(n):
		p[i] -= 1
	cycles = list()
	visited = set()
	for i in range(n):
		if i in visited:
			continue
		ptr = i
		visited.add(ptr)
		chain = s[ptr]
		while p[ptr] != i:
			ptr = p[ptr]
			chain += s[ptr]
			visited.add(ptr)
		clen = kmp(chain[1:] + chain, chain) + 1
		cycles.append(clen)
	out = 1
	for n in cycles:
		out = lcm(out, n)
	print(out)

def pi(pat):
	p = [0] * len(pat)
	for i in range(1, len(pat)):
		j = p[i - 1]
		while j and pat[i] != pat[j]:
			j = p[j - 1]
		if pat[i] == pat[j]:
			j += 1
		p[i] = j
	return p

def kmp(target, pattern):
	p = pi(pattern)
	j = 0
	for i in range(len(target)):
		while j and target[i] != pattern[j]:
			j = p[j - 1]
		if target[i] == pattern[j]:
			j += 1
		if j == len(pattern):
			return i - len(pattern) + 1
	return -1

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	return x * y // gcd(x, y)
for _ in range(int(input())):
	solve()


from math import gcd

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

def shift(s):
	for i in range(1, len(s) + 1):
		if s[i:] + s[:i] == s:
			return i
t = int(input())
while t:
	t -= 1
	n = int(input())
	s = [x for x in input()]
	p = [int(x) for x in input().split()]
	trans = [0] * (n + 1)
	for i in range(n):
		trans[p[i]] = i + 1
	res = []
	cir = [0] * (n + 1)
	for i in range(1, n + 1):
		if cir[i] != 0:
			continue
		flag = 0
		x = trans[i]
		tmp = [i]
		string = s[i - 1]
		while x != i:
			tmp.append(x)
			string += s[x - 1]
			x = trans[x]
		tmpans = shift(string)
		for x in tmp:
			cir[x] = tmpans
	ans = cir[1]
	for x in cir[2:]:
		ans = lcm(ans, x)
	print(ans)


from sys import stdin
input = stdin.readline
from math import gcd

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

def f(s, a):
	cnt = 0
	cycles = []
	vis = [-1] * len(a)
	for i in range(len(a)):
		if vis[i] == -1:
			cur = []
			node = i
			while vis[node] == -1:
				cur.append(node)
				vis[node] = cnt
				node = a[node]
			cycles.append(cur)
			cnt += 1
	ans = 1
	for cycle in cycles:
		start = [s[i] for i in cycle]
		cnt = 1
		t = [start[-1]] + start[:len(start) - 1]
		while t != start:
			cnt += 1
			t = [t[-1]] + t[:len(t) - 1]
		ans = lcm(ans, cnt)
	return ans
for _ in range(int(input())):
	n = input()
	s = input().strip()
	a = list(map(lambda s: int(s) - 1, input().strip().split()))
	print(f(s, a))


class zAlgorithm:

	def __init__(self, s):
		self.sdat = list(map(lambda x: ord(x), s))
		self.sl = len(s)
		self.res = [0] * self.sl
		self.res[0] = self.sl
		(i, j) = (1, 0)
		while i < self.sl:
			while i + j < self.sl:
				if self.sdat[j] != self.sdat[i + j]:
					break
				j += 1
			self.res[i] = j
			if j == 0:
				i += 1
				continue
			k = 1
			while i + k < self.sl and k + self.res[k] < j:
				self.res[i + k] = self.res[k]
				k += 1
			i += k
			j -= k

def do():
	import math

	def lcm(x, y):
		return x * y // math.gcd(x, y)
	n = int(input())
	s = input()
	dat = list(map(int, input().split()))
	for i in range(len(dat)):
		dat[i] -= 1
	visited = [False] * n
	cycles = []
	ans = 1
	for i in range(n):
		if visited[i]:
			continue
		route = []
		cur = i
		while visited[cur] is False:
			visited[cur] = True
			route.append(s[cur])
			cur = dat[cur]
		instr = ''.join(route * 2)
		zres = zAlgorithm(instr)
		ind = 1
		while zres.res[ind] < len(route):
			ind += 1
		ans = lcm(ans, ind)
	print(ans)
q = int(input())
for _ in range(q):
	do()


import string
s0 = string.ascii_lowercase

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

def lcm(x, y):
	return x * y // gcd(x, y)
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = list(map(int, input().split()))
	res = []
	flag = [False] * n
	for i in range(n):
		if flag[i]:
			continue
		flag[i] = True
		cur = p[i] - 1
		curs = s[i]
		while cur != i:
			curs += s[cur]
			cur = p[cur] - 1
			flag[cur] = True
		prev = str(curs)
		cur_res = 1
		curs = curs[-1] + curs[0:len(curs) - 1]
		while prev != curs:
			curs = curs[-1] + curs[0:len(curs) - 1]
			cur_res += 1
		res.append(cur_res)
	result = 1
	for i in range(len(res)):
		result = lcm(result, res[i])
	print(result)