## Conveyor solution codeforces

There is a conveyor with 120120 rows and 120120 columns. Each row and column is numbered from 00 to 119119, and the cell in 𝑖i-th row and 𝑗j-th column is denoted as (𝑖,𝑗)(i,j). The top leftmost cell is (0,0)(0,0). Each cell has a belt, and all belts are initially facing to the right.

Initially, a slime ball is on the belt of (0,0)(0,0), and other belts are empty. Every second, the state of the conveyor changes as follows:

• All slime balls on the conveyor move one cell in the direction of the belt at the same time. If there is no cell in the moved position, the slime gets out of the conveyor, and if two slime balls move to the same cell, they merge into one.
• All belts with slime ball in the previous second change direction at the same time: belts facing to the right become facing to the down, and vice versa.
• A new slime ball is placed on cell (0,0)(0,0).

There are 𝑞q queries, each being three integers 𝑡t𝑥x, and 𝑦y. You have to find out if there is a slime at the cell (𝑥,𝑦)(x,y) after 𝑡t seconds from the start. Can you do it?

## Conveyor solution codeforces

Input

The first line contains one integer 𝑞q (1𝑞1041≤q≤104) — the number of queries.

The only line of each query contains three integers 𝑡t𝑥x, and 𝑦y (0𝑡10180≤t≤10180𝑥,𝑦<1200≤x,y<120).

Output

Print the answer for each test case, one per line. If there is a slime ball in the cell (𝑥,𝑦)(x,y) after 𝑡t seconds from the initial state, print “YES“. Otherwise, print “NO“.

Example

input

Copy
6
1 1 0
5 1 3
0 0 0
2 4 5
2 0 2
1547748756 100 111

output

Copy

## Conveyor solution codeforces

NO
YES
YES
NO
YES
YES

Note

The state of conveyor with 𝑡=0t=0. Red arrow represents the direction of each belt, and blue figure represents slime.

The state of conveyor with 𝑡=1t=1.

The state of conveyor with 𝑡=2t=2.