Farmer John's cows scattered across a huge pasture, represented as a 2D grid (chessboard). Placement of cows is very entertaining. For each cell (
x,
y) c
\(x>=0\) and
\(y>=0\), there is a cow in cell (
x,
y), if for all integers
\(k>=0\), the remainders
\(\lfloor {\frac {x}{3^k} }\rfloor\) and
\(\lfloor {\frac {y}{3^k} }\rfloor\ ) modulo 3 have the same parity. In other words, these remainders are both odd (equal to 1) or both even (equal to 0 or 2). For example, cells for
\(0<=x,y<9\) that contain cows are labeled 1 in the figure below.
x
012345678
0 101000101
1 010000010
2 101000101
3 000101000
y4000010000
5 000101000
6 101000101
7 010000010
8 101000101
Farm John is interested in how many cows are present in a certain square region of his pasture. It asks
Q questions, each containing three integers
xi,
yi,di. For each question, Farmer John wants to know how many cows are in the cells with (xi, yi) to (xi+di, yi+di) (including endpoints).
Input
The first line contains Q (\(1<=Q<=10^4\)) - the number of questions.
Each of the following Q lines contains 3 integers di, xi, and yi (\(0<=x_i,y_i,d_i<=10 ^{18}\)).
Imprint
Q lines, one for each question - one integer - the answer.
Examples
| # |
Input |
Output |
| 1 |
8
1000
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000 |
11
0
4
3
1
2
2
1000000000000000001 |