Once In My Life

题目描述

对于小 A 而言，数位包含 $1 ∼ 9$，并且至少两个数位是 $d（1 ≤ d ≤ 9）$的十进制正整数都是幸运数。 当 $d = 3$ 时，显然 $1234567890123$ 是小 A 的幸运数，但 $987654321$ 因为数位 $3$ 仅出现了一次而不是幸运数，$998244353$ 因为缺少数位 $1, 6, 7$ 而不是幸运数。 现在小 A 有一个正整数 $n$，并给出正整数 $d$。他想找到正整数 $k$ 使得二者的乘积 $n \times k$ 是幸运数。你能用计算机辅助他的计算吗？

输入格式

本题包含多组测试数据1。 第一行，一个正整数 $T（1 ≤ T ≤ 3 × 10^5）$，表示数据组数。 对于每组数据： 一行，两个正整数 $n, d（1 ≤ n ≤ 10^8，1 ≤ d ≤ 9）$。

输出格式

对于每组数据： 输出一行，一个正整数 $k$，满足 $n \times k$ 是幸运数。你需要保证 $k ≤ 2 × 10^{10}$。

样例 #1

样例输入 #1

3
1 6
12345678 9
233 2

样例输出 #1

1234567896
404
9217006

提示

对于 $n = 1，d = 6$，可以取 $k = 1234567896$，有 $n · k = 1234567896$ 为幸运数。 对于 $n = 12345678，d = 9$，可以取 $k = 404$，有 $n · k = 4987653912$ 为幸运数。 对于 $n = 233，d = 2$，可以取 $k = 9217006$，有 $n · k = 2147562398$ 为幸运数。