7.0 Ryn Blackwood’s Adventures: Endgame
At long last, Ryn Blackwood reaches the heart of the ancient cavern — a crystal altar pulsing with eerie rhythm. Upon it lies a final test: A string of luminous runes s, perfectly ordered, and beside it a shifting magical sequence p, a permutation spell of length n.
When Ryn channels her magic through the spell, the runes are rearranged and every position i in the string moves to position p[i].
For example, with
s = "krqx" and p = [3,1,4,2], one casting transforms it into "qkxr".
Provided that it is always possible, help Ryn find the minimum number of times the spell must be cast for the string to return to its original form.
(A permutation of length n contains all numbers from 1 to n in any order, each number occurring once)
Constraints
1 ≤ t ≤ 5000
1≤n≤200
1<=p[i]<=n
Input Format
Each test contains multiple test cases.
The first line contains an integer t — the number of test cases (1 ≤ t ≤ 5000).
The description of each test case follows.
The first line of each test case contains an integer n 1≤n≤200 — the length of s
The second line contains the string s (all lower case)
The third line contains p (1<=p[i]<=n)
Output Format
output single integer — the minimum number of spells, after which the string s will become the same as it was before
Example 1
Input:
2
5
ababa
3 4 5 2 1
5
ababa
2 1 4 5 3
Output:
1
6
Explanation:
In the first sample, the spell doesn't change the string, so it will become the same as it was after
1 operation.
In the second sample the string will change as follows:
s= babaa
s= abaab
s= baaba
s= abbaa
s= baaab
s = ababa
Log In to solve the Question