Коровы Фермера Джона разбрелись по огромному пастбищу, представленному в виде 2D-решётки (шахматной доски). Размещение коров весьма занимательно. Для каждой ячейки (
x,
y) с
\(x>=0\) и
\(y>=0\), существует корова в ячейке (
x,
y), если для всех целых чисел
\(k>=0\), остатки
\(\lfloor {\frac {x}{3^k} }\rfloor\) и
\(\lfloor {\frac {y}{3^k} }\rfloor\) по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 1) или оба чётные (равны 0 или 2). Например, ячейки для
\(0<=x,y<9\), которые содержат коров обозначены цифрой 1 на рисунке ниже.
x
012345678
0 101000101
1 010000010
2 101000101
3 000101000
y 4 000010000
5 000101000
6 101000101
7 010000010
8 101000101
Ферме Джон интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт
Q вопросов, кажый содержит три целых числа
xi,
yi,
di. Для каждого вопроса Фермер Джон хочет знать, сколько коров в ячейках с (
xi,
yi) до (
xi+
di,
yi+
di) (включая конечные точки).
Входные данные
Первая строка содержит
Q (
\(1<=Q<=10^4\)) - количество вопросов.
Каждая из следующих
Q строк содержит 3 целых числа
di,
xi, и
yi (
\(0<=x_i,y_i,d_i<=10^{18}\)).
Выходные данные
Q строк, по одной для каждого вопроса - одно целое число - ответ.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8
10 0 0
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 |