← 返回题目列表

Codeforces · 1690/F

F. 移动字符串

中文机器翻译题面 查看原题

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$$$,因此他将 $$$s$$$ 替换为字符串 $$$new$$$,其中对于从 $$$1$$$ 到 $$$n$$$ 的任何 $$$i$$$,$$$new_i = s_{p_i}$$$ 是正确的。例如$$$s=wmbe$$$和$$$p = [3, 1, 4, 2]$$$,运算后字符串将变为$$$s=s_3 s_1 s_4 s_2=bwem$$$。

Polycarp 想知道经过多少次操作后该字符串将首次等于其初始值。由于可能需要很长时间,他请求你在这件事上提供帮助。

可以证明所需的操作次数总是存在的。它可能非常大,因此请使用 64 位整数类型。

输入

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

每个 case 的第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 200$$$) — 字符串的长度和排列。

每个 case 的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,包含小写拉丁字母。

每个 case 的第三行包含 $$$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

注意

在第一个示例操作中,不会更改字符串,因此它将变得与 $$$1$$$ 操作后的字符串相同。

在第二个示例中,字符串将更改如下:

- $$$s$$$ = 巴巴
- $$$s$$$ = abaab
- $$$s$$$ = baaba
- $$$s$$$ = abbaa
- $$$s$$$ = baaab
- $$$s$$$ = 贝巴