题目描述

我们定义一个正整数的位数为 $k$ 的倍数 ，且每一位都是 $9$ 的数字为 $k$ 阶 "ZCX" 数。

现在我们要问你 $T$ 个问题，我们每次给出两个正整数 $n,k$ ，请你告诉 小Z 能不能把正整数 $n$ 拆分成若干个 $k$ 阶 "ZCX" 数的和。

如果可以拆分请输出 $1$ ，不可以请输出 $0$ 。

输入格式

第 $1$ 行输入数字 $T$ 表示询问次数

第 $2$ 行 到 $T + 1$ 行，每行给出两个数 $n,k$ 。

输出格式

如果正整数 $n$ 可以拆分成 $k$ 阶 "ZCX" 数 请输出 $1$ ，不可以请输出 $0$ 。

样例

3
9999 1
9999 2
9999 3

1
1
0

数据规模与约定

对于 $50\%$ 的数据保证：$1 \le T \le 1000 , 1 \le n \le 10^6 , k = 1$ 。 对于 $100\%$ 的数据保证：$1 \le T \le 1000 , 1 \le n \le 10^{11} , 1 \le k \le 10$ 。