#GYM104651G. GCD of Pattern Matching
GCD of Pattern Matching
Description
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 < d_{n - 1} < m$, and $\forall_{i = 0, 1, \ldots, n - 2} 0 \leq d_i < 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.
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.
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).
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).
5
10 ccpcccpc
10 cpcpcp
10 cpc
4 cpccpc
4 dhcp
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$.