Коровы Фермера Джона разбрелись по огромному пастбищу, представленному в виде 2D-решётки (шахматной доски).
Размещение коров весьма занимательно. Для каждой ячейки (x, y) с x ≥ 0 и y ≥ 0, существует корова в ячейке (x, y) если для всех целых чисел k ≥ 0, остатки ⌊x / 3^k
⌋ и ⌊y / 3^k
⌋ по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 1) или оба чётные (равны 0 или 2). Например, ячейки для 0 ≤ x, y < 9, которые содержат коров обозначены цифрой 1 на рисунке ниже.
ФД интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт q вопросов, кажый содержит три целых числа x[i]
, y[i]
, d[i]
. Для каждого вопроса ФД хочет знать, сколько коров в ячейках (x[i]
, y[i]
) до (x[i]
+ d[i]
, y[i]
+ d[i]
) (включая конечные точки).
Первая строка содержит q (1 ≤ q ≤ 10^4
) - количество вопросов.
Каждая из следующих q строк содержит 3 целых числа d[i]
, x[i]
и y[i]
(0 ≤ x[i]
, y[i]
, d[i]
≤ 10^18
).
Выведите q строк, по одной для каждого вопроса - одно целое число - ответ.