Counting Diagonal Cows

Farmer John's cows are spread out on his vast rectangular pasture, which can be viewed as an infinite 2D grid of unit squares (think of a huge chessboard). For every grid cell with coordinates \(x\ge0\) and \(y\ge0\), there is a cow in that cell if and only if for every integer \(k\ge0\), the remainders when \(\lfloor \frac{x}{3^k} \rfloor\) and \(\lfloor \frac{y}{3^k} \rfloor\) are divided by 3 have the same parity. In other words, the cell contains a cow if both remainders are odd (equal to 1) or both are even (either 0 or 2).

Farmer John is interested in the number of cows that lie on the diagonal of a specific square region of his field. He performs \(Q\) queries. Each query is given by three integers \(x_i, y_i, d_i\). For each query, you must determine how many cows lie on the diagonal of the square whose bottom-left corner is \((x_i,y_i)\) and top-right corner is \((x_i+d_i, y_i+d_i)\). The diagonal is defined by the cells \((x_i+j, y_i+j)\) for \(0\le j\le d_i\), inclusive.

inputFormat

The first line of input contains a single integer \(Q\) representing the number of queries. Each of the next \(Q\) lines contains three space-separated integers \(x_i\), \(y_i\), and \(d_i\).

Constraints:

• \(x_i, y_i \ge 0\)
• \(d_i \ge 0\)

outputFormat

For each query, output a single integer on a new line representing the number of cows on the diagonal of the queried square region.

sample

1
0 0 2

3