G. GCD of Pattern Matching
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For any positive integer $$$x$$$, its $$$m$$$-based representation is a string of digits $$$d_{n - 1} d_{n - 2} \cdots d_1 d_0$$$ where $$$x = \sum_{i = 0}^{n - 1}{d_i m^i}$$$, $$$0 \lt d_{n - 1} \lt m$$$, and $$$\forall_{i = 0, 1, \ldots, n - 2} 0 \leq d_i \lt m$$$.

Let $$$\Sigma$$$ be the set of all possible characters. We call that a string $$$S = s_1 s_2 \cdots s_n$$$ matches with a pattern $$$P = p_1 p_2 \cdots p_n$$$ if and only if there exists a mapping function $$$f: \Sigma \to \Sigma$$$ such that $$$\forall_{i = 1, 2, \ldots, n} f(s_i) = p_i$$$ and $$$\forall_{a, b \in \Sigma, a \neq b} f(a) \neq f(b)$$$.

Given an integer $$$m$$$ and a pattern $$$P$$$ consisting of lowercase English letters, find all positive integers in $$$m$$$-based representation that match the pattern, and report their greatest common divisor (GCD) in 10-based representation.

It is guaranteed for each test case that there always exists at least one integer whose $$$m$$$-based representation matches the pattern.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \leq T \leq 500\,000$$$), denoting the number of test cases.

Each of the following $$$T$$$ lines describes a test case and contains an integer $$$m$$$ and a string $$$P$$$ ($$$2 \leq m \leq 16$$$, $$$1 \leq |P| \leq 16$$$), separated by a single space.

Output

For each of the $$$T$$$ test cases, print a single line containing a single integer: the GCD of all matched positive integers (in 10-based representation).

Example
Input
5
10 ccpcccpc
10 cpcpcp
10 cpc
4 cpccpc
4 dhcp
Output
10001
10101
1
65
3
Note

For the last sample case, all integers of length $$$4$$$ with no duplicate digits in $$$4$$$-based representation can match $$$\texttt{dhcp}$$$, whose digits have a constant sum $$$0 + 1 + 2 + 3 = 6$$$ (e.g. $$$\texttt{1023}$$$, $$$\texttt{1302}$$$, $$$\texttt{3210}$$$). Together with $$$\sum_{i = 0}^{n - 1}{d_i 4^i} \equiv \sum_{i = 0}^{n - 1}{d_i} \pmod 3$$$ and $$$\gcd(1023, 3210) = 3$$$, we can conclude the answer is $$$3$$$.