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