소 세기

농부 존의 소들은 그의 가장 큰 목초지 곳곳에 흩어져 있다. 이 목초지는 거대한 2차원 격자, 즉 아주 큰 체스판과 같은 정사각형 칸들로 볼 수 있다.

목초지에 놓인 소들의 패턴은 흥미롭다. 모든 $x\ge 0$, $y\ge 0$인 칸 $(x,y)$에 대해, 모든 정수 $k\ge 0$에서 $\left\lfloor \frac{x}{3^k}\right\rfloor$를 3으로 나눈 나머지와 $\left\lfloor \frac{y}{3^k}\right\rfloor$를 3으로 나눈 나머지의 홀짝이 같으면 $(x,y)$에 소가 있다. 즉 두 나머지가 모두 홀수(1)이거나, 모두 짝수(0 또는 2)이면 된다. $0\le 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

농부 존(FJ)은 목초지의 일부 영역에 소가 몇 마리 있는지 알고 싶어 한다. $Q$개의 질의가 주어지며, 각 질의는 정수 $x_i$, $y_i$, $d_i$로 이루어진다. 각 질의마다 $(x_i,y_i)$에서 $(x_i+d_i,y_i+d_i)$까지 대각선 방향으로 놓인 칸들(양 끝 포함)에 있는 소의 수를 구한다.

첫 줄에 질의의 개수 $Q$ ($1\le Q\le 10^4$)가 주어진다. 이어서 $Q$개의 줄에 세 정수 $d_i$, $x_i$, $y_i$ ($0\le x_i,y_i,d_i\le 10^{18}$)가 한 줄에 하나씩 주어진다.

$Q$개의 줄에 각 질의의 답을 한 줄에 하나씩 출력한다.