如同平常一样，Farmer John 的奶牛们分散在他的最大的草地上。草地可以看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。奶牛分布在草地上的方式相当迷人。对于每一个满足 x≥0 以及 y≥0的方格 (x,y)，当对于所有整数 k≥0，⌊ ${x \over 3^k}$ ⌋ 和 ⌊ ${y \over 3^k}$ ⌋ 除以三的余数的奇偶性均相同时，有一头奶牛位于 (x,y)。换言之，两个余数均为奇数（均等于 1），或均为偶数（均等于 0 或 2）。例如，满足 0≤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 对他的草地上的某个特定区域内的奶牛数量感兴趣。他进行了 QQ 个询问，每个询问由三个整数 x$_i$,y$_i$,d$_i$ 组成。对每个询问，FJ 想要知道有多少奶牛位于 (x$_i$,y$_i$) 至 (x$_i$+d$_i$,y$_i$+d$_i$) 的对角线上的方格内（包括两端）。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 Q（1≤Q≤10$^4$），为询问的数量。以下 Q行每行包含三个整数 d$_i$，x$_i$ 和 y$_i$（0≤x$_i$,y$_i$,d$_i$≤$10^{18}$）。

输出格式（输出至终端 / 标准输出）：

输出 QQ 行，每个询问输出一行。

输入样例：

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

测试点性质：

• 测试点 2 满足对于每一个询问有 di≤100。
• 测试点 3-6 满足对于每一个询问有 x+d=3$^{30}$-1以及 y=0。
• 测试点 7-12 没有额外限制。