As is typical, Farmer John's cows have spread themselves out along his largest pasture, which can be regarded as a large 2D grid of square "cells" (picture a huge chessboard).
The pattern of cows across the pasture is quite fascinating. For every cell (x, y) with x ≥ 0 and y ≥ 0, there exists a cow at (x, y) if for all integers k ≥ 0, the remainders when ⌊x / 3^k
⌋ and ⌊y / 3^k
⌋ are divided by three have the same parity. In other words, both of these remainders are odd (equal to 1), or both of them are even (equal to 0 or 2). For example, the cells satisfying 0 ≤ x, y < 9 that contain cows are denoted by ones in the diagram below.
FJ is curious how many cows are present in certain regions of his pasture. He asks q queries, each consisting of three integers x[i]
, y[i]
, d[i]
. For each query, FJ wants to know how many cows lie in the cells along the diagonal range from (x[i]
, y[i]
) to (x[i]
+ d[i]
, y[i]
+ d[i]
) (endpoints inclusive).
The first line contains q (1 ≤ q ≤ 10^4
), the number of queries.
The next q lines each contain three integers d[i]
, x[i]
and y[i]
(0 ≤ x[i]
, y[i]
, d[i]
≤ 10^18
).
Print q lines, one for each query.