Hide

Problem N
Turning Trominos

/problems/turningtrominos/file/statement/en/img-0001.png
$L$-trominos, replicated.

The $L$-tromino is composed of three unit squares arranged as shown in part A of the illustration to the right. The $L$-tromino is also an example of a rep-tile because four $L$-trominos can be arranged to make a replica of itself that is twice as tall and twice as wide, as shown in B. Rep-tiles are interesting because, once they can tile themselves, they can recursively tile as much of the plane as we want, as suggested in C and D. Part C is made from four copies of B, and D is made from four copies of C. Figure 1 shows the first quadrant of the plane completely tiled by $L$-trominos by repeating the same procedure.

For this problem, you will be given a square in the first quadrant, and your task is to find the orientation of the $L$-tromino covering that square. The unit squares of the first quadrant are numbered $0, 1, 2, \ldots $ in the $x$- and $y$-directions, as shown. The dots, in order from left to right, correspond to the first four sample inputs.

\includegraphics[width=0.3\textwidth ]{tileplane2.png}
Figure 1: $L$-trominos tiling the first quadrant.
\includegraphics[width=0.25\textwidth ]{orientations.png}
Figure 2: $L$-tromino orientations.

Input

The first line contains an integer $n$ $(1 \leq n \leq 10\, 000)$, indicating the number of cases that follow. Each case consists of a single line. Each of the next $n$ lines contains two integers $x$ and $y$, separated by a space, with $0\leq x,y\leq 2^{60}$, indicating a particular square in the first quadrant.

Output

For each case, output the orientation of the $L$-tromino that covers the given square, one line per case, where the orientations are shown in Figure 2.

Sample Input 1 Sample Output 1
5
0 0
1 3
2 7
7 12
100 100
0
1
2
3
0

Please log in to submit a solution to this problem

Log in