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)\)