CF1690F.Shifting String

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.

Polycarp 找到了一个字符串 $s$ 和一个排列 $p$，它们的长度恰好相同，均为 $n$。

一个 $n$ 元排列是指一个长度为 $n$ 的数组，其中每个从 $1$ 到 $n$ 的整数恰好出现一次。例如，$[1, 2, 3]$ 和 $[4, 3, 5, 1, 2]$ 是排列，但 $[1, 2, 4]$、$[4, 3, 2, 1, 2]$ 和 $[0, 1, 2]$ 不是。

在一次操作中，他可以将 $s$ 与 $p$ 相乘，即用字符串 $new$ 替换 $s$，其中对任意 $i$（$1 \le i \le n$）均有 $new_i = s_{p_i}$。例如，当 $s = \text{wmbe}$ 且 $p = [3, 1, 4, 2]$ 时，执行一次操作后字符串变为 $s = s_3 s_1 s_4 s_2 = \text{bwem}$。

Polycarp 想知道：最少经过多少次操作后，字符串首次变回其初始值？由于该数值可能非常大，他请求你帮助解决这一问题。

可以证明：满足条件的操作次数一定存在。该数值可能极大，因此请使用 64 位整数类型。

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.

输入的第一行包含一个整数 $t$（$1 \le t \le 5000$）—— 表示输入中测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 200$）—— 表示字符串和排列的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

每个测试用例的第三行包含 $n$ 个整数 —— 排列 $p$（$1 \le p_i \le n$），所有 $p_i$ 互不相同。

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.

输出 $t$ 行，每行包含对应输入测试用例的答案。答案为一个整数——使字符串 $s$ 经过操作后恢复为操作前状态所需的最少操作次数。

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

在第一个样例中，操作不会改变字符串，因此经过 $1$ 次操作后字符串将保持不变。

在第二个样例中，字符串的变化过程如下：

• $s$ = babaa
• $s$ = abaab
• $s$ = baaba
• $s$ = abbaa
• $s$ = baaab
• $s$ = ababa