Shifting String
Contest: Codeforces Round 797 (Div. 3)
Difficulty rating: 1700
Tags: graphs, math, number theory, strings

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 format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example 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

Example output:
1
6
12

Editorial:
To begin with, let's understand why the string will return to its original form. In fact, the graph that the permutation sets consists of simple cycles and it turns out that after a certain number of operations, each character will return to its place.
Consider each cycle as a string that is cyclically shifted every turn. It may seem that the answer is  — $$$lcm$$$ (the smallest common multiple) of the cycle lengths, but to become equal to the initial string, it is not necessary to go through the entire cycle. The constraints allow us to calculate the length of the minimum suitable shift $$$k_j$$$ in $$$\mathcal{O}(len^2)$$$, where $$$len$$$ is the length of the cycle, so just iterate over the desired shift. Note that after $$$k_j$$$ operations, the cycle will return to its original form and this will happen again after $$$k_j$$$ operations.
The answer will be $$$lcm$$$ of all $$$k_j$$$, since each cycle individually comes to its original form after the number of operations is a multiple of its $$$k_j$$$.