### devss's blog

By devss, 7 weeks ago,

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

• -1

 » 7 weeks ago, # | ← Rev. 3 →   +18 This is an interesting question, I don't understand why people vote for a novice programmer so negatively. they just try to ask you interesting questions that they run into.
 » 7 weeks ago, # |   0 interesting problem
•  » » 7 weeks ago, # ^ |   +1 *tokhmi problem
 » 7 weeks ago, # |   -15 I don't care how bullshit this problem is. But seriously, work on your English, bro.
 » 7 weeks ago, # |   +15 Please don't write problem statements inside of code formatting, it makes it much harder to read.