Поликарп нашёл строку \(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\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите единственное число — минимальное количество операций, после которого строка \(s\) станет такой же, какой была до их применения.
Примечание
В первом наборе входных данных применение операции не изменяет строку, поэтому она станет равной самой себе после \(1\) операции.
Во втором наборе входных данных строка будет меняться следующим образом:
- \(s\) = babaa
- \(s\) = abaab
- \(s\) = baaba
- \(s\) = abbaa
- \(s\) = baaab
- \(s\) = ababa