Genius Number Decomposition

A positive integer is called a \(k\)-genius number if and only if its number of digits is a multiple of \(k\) and every digit is \(9\). In other words, a \(k\)-genius number has the form:

\(10^{m\cdot k} - 1\)

for some positive integer \(m\). For example, \(9999\) is a 2-genius number because it has 4 digits (which is a multiple of 2) and every digit is \(9\); however, \(999\) is not a 2-genius number, though it is both a 1-genius and a 3-genius number.

You are given \(t\) test cases. In each test case, two integers \(n\) and \(k\) are provided. Your task is to determine whether it is possible to decompose \(n\) as a sum of one or more \(k\)-genius numbers. Note that you are allowed to use the same genius number more than once.

Hint: Observe that any \(k\)-genius number is of the form \(10^{mk}-1\), and in particular the smallest \(k\)-genius number is \(10^k-1\). Thus, if \(n\) can be expressed as a sum of \(k\)-genius numbers, then \(n\) must be divisible by \(10^k-1\).

inputFormat

The first line contains a single integer \(t\) (\(1 \le t \le 10^4\)), the number of test cases.

Each of the following \(t\) lines contains two space-separated integers \(n\) and \(k\) (\(1 \le n \le 10^{18}\), \(1 \le k \le 18\)).

\(n\) is the number you want to decompose, and \(k\) defines what a \(k\)-genius number is.

outputFormat

For each test case, print a single line containing YES if it is possible to decompose \(n\) as a sum of \(k\)-genius numbers, and NO otherwise.

sample

3
99 1
9999 2
999 2

YES
YES
NO