对于任何正整数 $x$，其 $m$ 进制表示为一个数字串 $d_{n-1}d_{n-2} \dots d_1d_0$，其中 $x = \sum_{i=0}^{n-1} d_i m^i$，$0 < d_{n-1} < m$，且对于所有 $i=0, 1, \dots, n-2$ 满足 $0 \le d_i < m$。

令 $\Sigma$ 为所有可能字符的集合。我们称字符串 $S = s_1s_2 \dots s_n$ 与模式 $P = p_1p_2 \dots p_n$ 匹配，当且仅当存在一个映射函数 $f : \Sigma \to \Sigma$，使得对于所有 $i=1, 2, \dots, n$ 满足 $f(s_i) = p_i$，且对于所有 $a, b \in \Sigma$，$a \neq b$ 蕴含 $f(a) \neq f(b)$。

给定整数 $m$ 和由小写英文字母组成的模式 $P$，找出所有 $m$ 进制表示与该模式匹配的正整数，并报告它们在 10 进制表示下的最大公约数 (GCD)。

题目保证对于每个测试用例，至少存在一个 $m$ 进制表示与该模式匹配的整数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 500\,000$)，表示测试用例的数量。

接下来的 $T$ 行，每行描述一个测试用例，包含一个整数 $m$ 和一个字符串 $P$ ($2 \le m \le 16$，$1 \le |P| \le 16$)，两者之间由一个空格分隔。

输出格式

对于每个测试用例，输出一行，包含一个整数：所有匹配的正整数的 GCD（以 10 进制表示）。

样例

输入 1

5
10 ccpcccpc
10 cpcpcp
10 cpc
4 cpccpc
4 dhcp

输出 1

10001
10101
1
65
3

说明

对于最后一个样例，所有长度为 4 且在 4 进制表示下无重复数字的整数都可以匹配 dhcp，这些数字的数位之和均为 $0 + 1 + 2 + 3 = 6$（例如 $1023, 1302, 3210$）。结合 $\sum_{i=0}^{n-1} d_i 4^i \equiv \sum_{i=0}^{n-1} d_i \pmod 3$ 以及 $\gcd(1023, 3210) = 3$，我们可以得出答案为 3。