编程题
### 问题描述
设 $f(m)$ 为所有 $m$ 进制正整数连接起来构造的一个 $m$ 进制无理数。
$f(10)$ 如下所示：
$$
0.123456789101112131415161718192021 \ldots
$$
可以看出小数点后第 $12$ 位数字是 $1$。
给定若干次询问，每次询问给出两个整数 $n,m$，求 $f(m)$ 的第 $n$ 位的数字。
### 输入格式
第一行包含一个正整数 $T(1 \le T \le 10^{4})$，表示测试用例的数量。
每个测试用例只有一行，包含两个正整数 $n,m(1 \le n \le 10^{18}, 2 \le m \le 10)$。具体意义如题面所示。
### 输出格式
对于每个测试用例，输出一行一个整数，表示答案。
### 样例输入
```text
4
1000 10
200 3
300 4
10 5
```
### 样例输出
```text
3
2
1
2
```