[Solution] Shifting String Codeforces Solution

[Solution] Shifting String Codeforces Solution

F. Shifting String

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp found the string s$s$ and the permutation p$p$. Their lengths turned out to be the same and equal to n$n$.

A permutation of n$n$ elements — is an array of length n$n$, in which every integer from 1$1$ to n$n$ occurs exactly once. For example, [1,2,3]$[1,2,3]$ and [4,3,5,1,2]$[4,3,5,1,2]$ are permutations, but [1,2,4]$[1,2,4]$, [4,3,2,1,2]$[4,3,2,1,2]$ and [0,1,2]$[0,1,2]$ are not.

In one operation he can

Solution Click Below:-  CLICK HERE

 multiply s$s$ by p$p$, so he replaces s$s$ with string new$new$, in which for any i$i$ from 1$1$ to n$n$ it is true that newi=spi$ne{w}_i=s_{p_i}$. For example, with s=wmbe$s=wmbe$ and p=[3,1,4,2]$p=[3,1,4,2]$, after operation the string will turn to s=s3s1s4s2=bwem$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.

Shifting String Codeforces Solution

It can be proved that the required number of operations always exists. It can be very large, so use a 64-bit integer type.

Input

The first line of input contains one integer t$t$ (1≤t≤5000$1\le t\le 5000$) — the number of test cases in input.

The first line of each case contains single integer n$n$ (1≤n≤200$1\le n\le 200$) — the length of string and permutation.

The second line of each case contains a string s$s$ of length n$n$, containing lowercase Latin letters.

The third line of each case contains n$n$ integers — permutation p$p$ (1≤pi≤n$1\le p_i\le n$), all pi$p_i$ are different.

Output

Output t$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$s$ will become the same as it was before operations.