Shifting String

题意翻译

## 题意简述 给定一长为 $n$ 的字符串 $s$（下标从 $1$ 开始） 与 $1\sim n$ 的排列 $p$。定义 $s^0=s,s^k_i=s^{k-1}_{p_i}$。求最小的 $k>0$ 使 $s^k=s$。$t$ 组数据。 - $t\le 5000,n\le200$。

题目描述

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.

输入输出格式

输入格式

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 $ 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.

输入输出样例

输入样例 #1

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

输出样例 #1

1
6
12

说明

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

题目大意：
给定一个长度为 \( n \) 的字符串 \( s \)（下标从 1 开始）和一个由 \( 1 \) 到 \( n \) 的排列组成的数组 \( p \)。定义 \( s^0 = s \)，对于 \( k > 0 \)，\( s^k_i = s^{k-1}_{p_i} \)。求最小的 \( k > 0 \) 使得 \( s^k = s \)。共有 \( t \) 组数据。限制条件为 \( t \le 5000, n \le 200 \)。

输入输出数据格式：
- 输入格式：
- 第一行包含一个整数 \( t \)（\( 1 \le t \le 5000 \)），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数 \( n \)（\( 1 \le n \le 200 \)），表示字符串和排列的长度。
- 每个测试用例的第二行包含一个长度为 \( n \) 的字符串 \( s \)，只包含小写拉丁字母。
- 每个测试用例的第三行包含 \( n \) 个整数，表示排列 \( p \)（\( 1 \le p_i \le n \)），且所有的 \( p_i \) 都是不同的。
- 输出格式：
- 输出 \( t \) 行，每行包含对应输入测试用例的答案。输出一个整数，表示字符串 \( s \) 变回初始值的最小操作次数。

输入输出样例：
- 输入样例 #1：
```
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
```
- 输出样例 #1：
```
1
6
12
```题目大意： 给定一个长度为 \( n \) 的字符串 \( s \)（下标从 1 开始）和一个由 \( 1 \) 到 \( n \) 的排列组成的数组 \( p \)。定义 \( s^0 = s \)，对于 \( k > 0 \)，\( s^k_i = s^{k-1}_{p_i} \)。求最小的 \( k > 0 \) 使得 \( s^k = s \)。共有 \( t \) 组数据。限制条件为 \( t \le 5000, n \le 200 \)。 输入输出数据格式： - 输入格式： - 第一行包含一个整数 \( t \)（\( 1 \le t \le 5000 \)），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数 \( n \)（\( 1 \le n \le 200 \)），表示字符串和排列的长度。 - 每个测试用例的第二行包含一个长度为 \( n \) 的字符串 \( s \)，只包含小写拉丁字母。 - 每个测试用例的第三行包含 \( n \) 个整数，表示排列 \( p \)（\( 1 \le p_i \le n \)），且所有的 \( p_i \) 都是不同的。 - 输出格式： - 输出 \( t \) 行，每行包含对应输入测试用例的答案。输出一个整数，表示字符串 \( s \) 变回初始值的最小操作次数。 输入输出样例： - 输入样例 #1： ``` 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 ``` - 输出样例 #1： ``` 1 6 12 ```