Como es costumbre, las vacas del Granjero Juan se han repartido en un su pastizal más grande, el cual puede ser visto como una cuadrícula ~b_i~ dimensioanl grande de "celdas" cuadradas (image un tablero de ajedrez inmenso).

El patrón de vacas en el pastizal es bastante fascinante. Para cada celda ~(x,y)~ con ~x \geq 0~ y ~y \geq 0~, existe una vaca en ~(x,y)~ si para todos los enteros ~k \geq 0~, los residuos cuando ~\left\lfloor \frac{x}{3^k}\right\rfloor~ y ~\left\lfloor\frac{y}{3^k}\right\rfloor~ son divididos por tres tienen la misma paridad. En otras palabras, ambos de los residuos son impares (iguales a 1), o ambos de ellos son pares (iguales a 0 o a 2). Por ejemplo, las celdas que satisfacen ~0 \leq x,y < 9~ que contienen vacas están denotas por unos en el diagrama siguiente.

        x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

GJ tiene curiosidad de saber cuántas vacas están presentes en ciertas regiones de su pastizal. El hace ~Q~ preguntas, cada una consistiendo de tres enteros ~x_i, y_i, d_i~. Para cada pregunta, GJ quiere saber cuántas vacas yacen en las celdas a lo largo del rango diagonal de ~(x_i,y_i)~ a ~(x_i+d_i,y_i+d_i)~ (incluyendo los puntos extremos).

Entrada

• La primera línea contiene ~Q~, el número de preguntas.
• Cada una de las siguientes ~Q~ líneas contienen tres enteros ~d_i, x_i,~ y ~y_i~.

Salida

~Q~ líneas, una por cada pregunta.

Restricciones

• ~1 \leq Q \leq 10^4~
• ~0 \leq x_i, y_i, d_i \leq 10^{18}~

Ejemplo de Entrada

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

Ejemplo de Salida

11
0
4
3
1
2
2
1000000000000000001

USACO 2021 February Contest, Gold Problem 3. Count the Cows.