8046: Count the Cows

如同平常一样，Farmer John 的奶牛们分散在他的最大的草地上。

草地可以看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。

奶牛分布在草地上的方式相当迷人。

对于每一个满足 x≥0 以及 y≥0 的方格 (x,y)，当对于所有整数 k≥0，⌊x3k⌋ 和 ⌊y3k⌋ 除以三的余数的奇偶性均相同时，有一头奶牛位于 (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 对他的草地上的某个特定区域内的奶牛数量感兴趣。

他进行了 Q 个询问，每个询问由三个整数 xi,yi,di 组成。

对每个询问，FJ 想要知道有多少奶牛位于 (xi,yi) 至 (xi+di,yi+di) 的对角线上的方格内（包括两端）。

输入格式

输入的第一行包含 Q，为询问的数量。

以下 Q 行每行包含三个整数 di,xi 和 yi。

输出格式

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

数据范围

1≤Q≤10⁴
0≤xi,yi,di≤10¹⁸


As is typical, Farmer John's cows have spread themselves out along his largest pasture, which can be regarded as a large 2D grid of square "cells" (picture a huge chessboard).

The pattern of cows across the pasture is quite fascinating. For every cell (x,y)(x,y) with x≥0x≥0 and y≥0y≥0, there exists a cow at (x,y)(x,y) if for all integers k≥0k≥0, the remainders when ⌊x3k⌋⌊x3k⌋ and ⌊y3k⌋⌊y3k⌋ are divided by three have the same parity. In other words, both of these remainders are odd (equal to 11), or both of them are even (equal to 00 or 22). For example, the cells satisfying 0≤x,y<90≤x,y<9 that contain cows are denoted by ones in the diagram below.

        x
    012345678

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

FJ is curious how many cows are present in certain regions of his pasture. He asks QQ queries, each consisting of three integers xi,yi,dixi,yi,di. For each query, FJ wants to know how many cows lie in the cells along the diagonal range from (xi,yi)(xi,yi) to (xi+di,yi+di)(xi+di,yi+di) (endpoints inclusive).

SAMPLE INPUT:

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

SAMPLE OUTPUT:

11
0
4
3
1
2
2
1000000000000000001

Problem credits: Benjamin Qi