时空限制

1S/512M

题目描述

定义一种奇特的无限数字序列 $g(m)$，它的生成方式与数字的进制 $m$（$2 \le m \le 10$）有关。序列的构造规则如下：

1. 按顺序遍历所有正整数 $k = 1, 2, 3, \ldots$。
2. 对于每个整数 $k$，我们得到它在 $m$ 进制下的字符串表示，记为 $S$。
3. 然后，我们将字符串 $S$ 反转，得到一个新的字符串 $S_{rev}$。
4. 最后，我们将原字符串 $S$ 和反转后的字符串 $S_{rev}$ 拼接起来，形成一个更长的字符串 $S + S_{rev}$。

将所有正整数 $k=1, 2, 3, \ldots$ 生成的拼接字符串依次连接，就构成了无限序列 $g(m)$。

让我们以十进制（$m=10$）为例：

• $k=1$: $m$ 进制表示为 $1$。反转后是 $1$。拼接后得到 $11$。
• $k=2$: $m$ 进制表示为 $2$。反转后是 $2$。拼接后得到 $22$。
• ...
• $k=9$: $m$ 进制表示为 $9$。反转后是 $9$。拼接后得到 $99$。
• $k=10$: $m$ 进制表示为 $10$。反转后是 $01$。拼接后得到 $1001$。
• $k=11$: $m$ 进制表示为 $11$。反转后是 $11$。拼接后得到 $1111$。
• $k=12$: $m$ 进制表示为 $12$。反转后是 $21$。拼接后得到 $1221$。

将这些结果按顺序拼接，就形成了序列 $g(10) = 11 \; 22\; 33\; 44\; 55\; 66\; 77\; 88 \; 99 \; 1001\; 1111\; 1221\; \ldots \ldots$。

现在有若干次询问，每次给出一个整数 $n$ 和一个进制 $m$，请你找出并输出 $g(m)$ 的第 $n$ 位数字（从 $1$ 开始计数）。

格式

输入格式

第一行包含一个整数 $T$，表示询问的次数。

接下来 $T$ 行，每行包含两个整数 $n, m$。具体含义见题目描述。

输出格式

对于每个询问，输出一行，包含一个数字，表示 $g(m)$ 的第 $n$ 位的数字。

样例

样例输入 #1

5
1 10
18 10
19 10
22 10
26 10

样例输出 #1

1
9
1
1
1

数据规模

对于 $40\%$ 的数据，$1 \leq n \leq 10^6$，$m = 10$。

对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 10^{9}$，$2 \le m \le 10$。