Hide

Problem G
The Power of Substitution

A substitution cipher uses a substitution table that for each letter $x$ in the alphabet assigns another (possibly the same) letter $p[x]$ in the same alphabet. A message $m_1\, m_2\, m_3\, m_4$ is then encrypted as $E_ p(m_1\, m_2\, m_3\, m_4)=p[m_1]\, p[m_2]\, p[m_3]\, p[m_4]$. This only works if $p$ is one-to-one. That is, $p$ has the property that $p[x] = p[x’]$ only if $x=x’$.

Now consider the idea of iterating this, i.e., to encrypt the encryption by applying the substitution table again. We can therefore define substitution to the power $k$, denoted $E^ k_ p()$ by

\begin{eqnarray*} E^0_ p(m_1\ldots m_\ell ) & = & m_1\ldots m_\ell \\ E^{k+1}_ p(m_1\ldots m_\ell ) & = & E_ p(E^ k_ p(m_1\ldots m_\ell )) \end{eqnarray*}

Now, given $m_1\ldots m_\ell $, $c_1\ldots c_\ell $, and $p[]$, we might ask (and we will!) for a $k$ such that $E_ p^ k(m_1\ldots m_\ell ) = c_1\ldots c_\ell $.

In our case the alphabet will have $100$ symbols denoted $1, 2,\ldots , 100$. You will be given a message, $m$, a cryptotext, $c$, and a substitution table, $p$. You are to find a $k$ such that $E^ k_ p(c)=d$. Specifically, we want such a $k$ in the interval $0\leq k\leq 10^9$ (there will always be a solution for the test cases).

Input

The input starts with an integer $1 \le N \le 20$ on a line by itself. This is the number of test cases.

A test case consists of four lines: first a single integer $L$ which is the size of the message (at least $1$, at most $200$), second a line with $L$ numbers (the message $m$), third a line with $L$ numbers (the crypto text $c$) and finally a line with $100$ numbers giving the substitution table $p[]$ (the first number is $p[1]$, the second is $p[2]$ and so on).

You can assume that the numbers in the message and crypto text are all integers that are at least $1$ and at most $100$. You can assume the same for $p$, and furthermore that $p$ is one-to-one.

Output

For each test case output a single integer $k$ on a line by itself. This $k$ should be non-negative and at most $10^9$, and obviously satisfy $E^ k_ p(m)=c$.

Sample Input 1 Sample Output 1
2
3
1 2 3
4 5 6
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1
3
1 2 9
2 1 10
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 39 42 41 44 43 46 45 48 47 50 49 52 51 54 53 56 55 58 57 60 59 62 61 64 63 66 65 68 67 70 69 72 71 74 73 76 75 78 77 80 79 82 81 84 83 86 85 88 87 90 89 92 91 94 93 96 95 98 97 100 99
3
1

Please log in to submit a solution to this problem

Log in