Inspired by his c-hing John Conway in his new university, Justin made the Game of Creation.
In the game, there is an infinite two dimensional grid of cells. Each cell can be either living or dead. Initally, only cell $(0, 0)$ is living and the other cells are dead. After every time step, every cell will transition to a new state simultaneously according to the following rules:

• A dead cell will become alive if there is only one neighbouring living cell, otherwise it will remain dead. Two cells are neighbouring if and only if they share an edge or a corner.
• A living cell will always stay alive.

Each cell is addressed using the Cartesian system $(x, y)$, with the x-axis being horizontal.

After $10^{100}$ time steps, you are to answer $Q$ queries $-$ if cell $(x_i, y_i)$ is alive.

Input

The first line consists of an integer $Q$.
Then, $Q$ lines follow. The $i$-th line consists of two integers $x_i, y_i$.

Output

For each query, output 1 if that cell is living, otherwise 0, in a line.

Constraints

For all testcases: $1 \le Q \le 10^6$, $|x_i|, |y_i| \le 10^9$
Subtask 1 (3%): $|x_i| = |y_i|$
Subtask 2 (5%): $|x_i|, |y_i| \le 10$, $Q \le 100$
Subtask 3 (7%): $|x_i|, |y_i| \le 100$
Subtask 4 (10%): $max(|x_i|, |y_i|)$ is a power of two
Subtask 5 (25%): $|x_i|, |y_i| \le 1000$
Subtask 6 (15%): When both $|x_i|, |y_i|$ are written in binary, they are of the form of some number of ones followed by 10 unconstrained bits. Moreover, they have the same number of bits.
Subtask 7 (35%): No additional constraints