As we all know, Skyler & Marie are the most annoying creatures to ever exist in Albuquerque. They went shopping together one day. But, Marie is a shoplifter & steals items from stores.

She asks Skyler to help her steal a necklace that she really liked. Skyler accepts to help her, but she encounters a problem while doing so.

"I thought I made myself very clear."

She has a two-sided long ribbon in which there is a binary string K. On the other side, there is a decimal prime number M. In order to shoplift, she needs to find out if M divides the decimal equivalent of K

INPUT

• First line contains an integer T denoting the number of test cases. Then T test cases follows.
• The first line of each test case contains a binary string K. The second line of each test case contains a prime number. M.

OUTPUT

• For each test case print "YES" if M divides K else print "NO".

• 1 ≤ T ≤ 20
• 1 ≤|K| ≤10^5
• M is a prime number.
• 2 ≤ M <10⁶