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