题目描述

如同平常一样，Farmer John 的奶牛们分散在他的最大的草地上。草地可以看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。

奶牛分布在草地上的方式相当迷人。对于每一个满足 $x\ge 0$ 以及 $y\ge 0$ 的方格 $(x,y)$，当对于所有整数 $k\ge 0$，$\left\lfloor \frac{x}{3^k}\right\rfloor$ 和 $\left\lfloor \frac{y}{3^k}\right\rfloor$ 除以三的余数的奇偶性均相同时，有一头奶牛位于 $(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$ 组成。对每个询问，FJ 想要知道有多少奶牛位于 $(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$ 行，每个询问输出一行。

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

11
0
4
3
1
2
2
1000000000000000001

提示

测试点性质：

• 对于另外 $8\%$ 的数据，满足对于每一个询问有 $d_i\le 100$。
• 对于另外 $32\%$ 的数据，满足对于每一个询问有 $x+d=3^{30}-1$ 以及 $y=0$。
• 对于另外 $52\%$ 的数据，没有额外限制。

供题：Benjamin Qi