众所周知，对于任意 $n$，恰好存在四个 $n$ 位数（包括前导零），它们是自平方数：这些数的平方的末 $n$ 位与该数本身相等。这四个数总是以下四个无限序列的后缀：

...0000000000 ...0000000001 ...8212890625 ...1787109376

例如，$09376^2 = 87909376$，其末尾为 $09376$。

你需要计算“准自平方数”的数量：即满足其平方的末 $n$ 位中，每一位与该数对应位之间的（循环）距离均不超过 $d$ 的数。注意，我们认为数字 $0$ 和 $9$ 是相邻的，因此例如与数字 $8$ 距离不超过 $3$ 的数字有 $5, 6, 7, 8, 9, 0$ 和 $1$。

输入格式

输入文件的第一行包含测试用例的数量 $t$ ($1 \le t \le 72$)。接下来的 $t$ 行，每行包含一个测试用例：两个数字 $n$ ($1 \le n \le 18$) 和 $d$ ($0 \le d \le 3$)。

输出格式

对于每个测试用例，输出长度为 $n$ 且每一位与平方对应位的（循环）距离均不超过 $d$ 的准自平方数的数量，每个结果占一行。

样例

输入 1

2
5 0
2 1

输出 1

4
12

说明

在第二个样例中，这 $12$ 个准自平方数分别是：$00, 01, 10, 11, 15, 25, 35, 66, 76, 86, 90, 91$。