F. Движущаяся строка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп нашёл строку $$$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$$$, в которой для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ верно, что $$$new_i = s_{p_i}$$$. Например, при $$$s=wmbe$$$ и $$$p = [3, 1, 4, 2]$$$, после применения операции строка превратится в $$$s=s_3 s_1 s_4 s_2=bwem$$$.

Поликарпу стало интересно, через сколько операций строка впервые вернётся к своему первоначальному виду. Так как это может занять слишком много времени, он просит вашей помощи в этом вопросе.

Можно доказать, что искомое количество операций всегда существует. Оно может оказаться очень большим, используйте 64-битный целочисленный тип.

Входные данные

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных в тесте.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \le n \le 200$$$) — длину строки и перестановки.

Вторая строка каждого набора содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.

Третья строка каждого набора содержит $$$n$$$ целых чисел — перестановку $$$p$$$ ($$$1 \le p_i \le n$$$), все $$$p_i$$$ различны.

Выходные данные

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите единственное число — минимальное количество операций, после которого строка $$$s$$$ станет такой же, какой была до их применения.

Пример
Входные данные
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
6
12
Примечание

В первом наборе входных данных применение операции не изменяет строку, поэтому она станет равной самой себе после $$$1$$$ операции.

Во втором наборе входных данных строка будет меняться следующим образом:

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