In the Cat Kingdom, cats are everywhere.
One day, the king of Cat Kingdom wanted to know how many cats there are. However, there were too many cats, so the king divided the cats into t groups and calculated the number of cats in each group separately. In this way, he was wondering if he counts every n cats, can he complete the counting through all the cats in the group?
For example:
If he counts every 3 cats, then the process will be 3, 6, 9, 12... cats. However, he will not be able to complete the counting for 25 cats because there will be 1 cat left anyway.
The king wants you to help him write a program to check if he can count n cats at a time and no cats will be left in each group. Namely, cats can be divided by n with no remainder.
Hint:
Method to check if a number is multiple of n:
For 3: Sum the digits. The result must be divisible by 3.
For 4: The last two digits form a number that is divisible by 4
For 5: The last digit is 0 or 5.
For 6: It is divisible by 2 and by 3.
(7 is not included in this problem)
For 8: The last three digits form a number that is divisible by 8.
For 9: Sum the digits. The result must be divisible by 9.
For 11: Take the alternating sum of the digits from left to right in a given number. If the sum is divisible by 11, so is the original number. For example: 2728 has an alternating sum of digits 2 – 7 + 2 – 8 = -11. Since -11 is divisible by 11, so is 2728.
The first line contains an integer t, means how many group of cats should be counted.
The next t lines, each line contains two integer x, n, means the number of cats and how many cats should be counted at once.
for all testcase:
The output contains t lines, for each group of cats, if there are 0 cats left in the end, output "Yes", otherwise, output "No".