b-Huanchen Number

Given a very large positive integer N (in decimal) and a base b, define S as the digit sum of N in base b.

A number N is called a b-Huanchen number if and only if:

$$ N \bmod S = 0 $$

Your task is to determine whether N is a b-Huanchen number.

The input is guaranteed valid. In particular, N may be so large that it does not fit in any built-in C++ integer type.

Digit sum in base b

Write N in base b:

$$ N = (a_k a_{k-1}\dots a_1 a_0)_b $$

where each digit satisfies $0 \le a_i \lt b$. Then:

$$ S = a_0 + a_1 + \dots + a_k $$

Input

The first line contains an integer n, the number of values N.

Each of the next n lines N b with:

• a decimal string N
• an integer base b

Constraints (guaranteed):

• N is a positive integer written in decimal (no sign).
• b satisfies $2 \le b \le 36$.
• N can be extremely large (may exceed C++ basic data type limits).
• S fits in uint.

Subtasks:

• For the first 20% testcases: N fits in uint
• For another 30% testcases: b = 10

Output

n lines:

• YES if N is a b-Huanchen number;
• otherwise NO.

Sample

Input

1
12 10

Output

YES

Explanation

In base 10, the digit sum is 1 + 2 = 3, and 12 is divisible by 3.

Hint on array sizes

If you don't know how long the array is, you should consider using containers from C++ STL.