In this problem you have to answer $Q$ queries. In each query you are given two integers $N$ and $K$. You have to decide if it is possible to represent $N$ as the sum of exactly $K$ powers of 3 (they may or may not be distinct). If it is possible to represent $N$ in such a way then the answer for that query is "YES"(without quotes) otherwise it is a "NO" (without quotes).

Input Format

The first line contains a postive integer $Q$ - the number of queries. 

Each of the next $Q$ lines contains two space separated integers $N$ and $K$ .

Constraints

• $1 \leq Q \leq 10^7$
• $1 \leq N \leq 10^{18}$
• $1 \leq K \leq 10^{18}$

Output Format

For each query, print the answer to that query i.e. "YES"(without quotes) if it is possible to write $N$ as the sum of exactly $K$ powers of 3 else print "NO"(without quotes).