### 问题描述 农夫小齐的奶牛们分散在他最大的牧场里，可以看作是一个巨大的二维网格，形成了一个方格的“单元格”模式（可以想象成一个巨大的棋盘）。 对于每个坐标为 $(x, y)$，其中 $x \geq 0$ 且 $y \geq 0$ 的单元格，如果对于所有整数 $k \geq 0$，当将 $\lfloor x/3^k \rfloor$ 和 $\lfloor y/3^k \rfloor$ 分别除以三时的余数同奇同偶，那么该单元格上存在一头奶牛。换句话说，这两个余数都是奇数（等于 $1$），或者都是偶数（等于 $0$ 或 $2$）。 小齐对他的牧场的某些区域有多少头奶牛感到好奇。他提出了 $Q$ 个查询，每个查询包括三个整数 $x_i, y_i, d_i$。对于每个查询，小齐想知道在从 $(x_i, y_i)$ 到 $(x_i+d_i, y_i+d_i)$ 的对角线范围内有多少头奶牛（包括端点）。 ### 输入格式 第一行包含整数 $Q$，表示查询的数量。 接下来 $Q$ 行，每行包含三个整数 $d_i, x_i, y_i$。 ### 输出格式 输出 $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 ``` ### 评测数据规模 $1 \leq Q \leq 10^4$，$0 \leq x_i, y_i, d_i \leq 10^{18}$。