While playing a mental math game, you realize that the number k is mathematically beautiful.

You then realize that the number x can be mathematically beautiful if it is represented as a sum of a sequence where each element is a power of k and all the numbers in the sequence are different.

Task

Your task is to determine whether the number is mathematically beautiful.

Input format

• The first line contains T denoting the number of test cases.
• The next T lines contain \(x\)  and  \(k\)  denoting the numbers.

Output Format

For each test case, output  "YES"  if \(x\) is "mathematically beautiful" and  "NO"  otherwise.

Constraints

\(T <= 1000\)

\((1 <= x <= 10^{18})\)

\((2 <= k <= 9)\)