Hi my friends

From now on, I want to ask you new questions every few days that I had previously solved in theory, but because they were interesting questions, I put them on codeforces so that you can challenge your problem-solving skills. Most of these questions do not require much code and the main solution to these questions is the key to solving the question.

First question:

Mark and Mike are playing an interesting game with each other. Mark writes the natural numbers m to n on a piece of paper. In each step, Mike can delete three of these written numbers and write a^3+b^3+c^3 instead ( a , b , c are that three numbers). Mike can do as many steps as he wants.
Mark asks Mike q questions that consists of two values, x and y.
His request to Mike is to say, can he, by doing a number of steps, reach a state where only one number remains and that number is x^y ?

It is guaranteed that the amount of power given is between the minimum and maximum of these steps.

Input

The first contains three integers: q (1 ≤ q ≤ 2000).
The first line of each query contains m and n (that will make following sequence: m , (m+1) , (m+2) , … , (n-1) , n) (1 ≤ m ≤ 5000)(1 ≤ n ≤ 5000)
The second line of each query contains x and y ( which means x power y)

Output

Print “YES” if its possible else print “NO”.

Examples

Input

2
1 4
2 3
1 3
6 2

Output

NO
YES

The answer and code of this question will be posted on this page soon. Share your solutions.