Cho một bảng có kích thước vô hạn, các hàng và các cột đánh số từ 0.

Ô ở hàng \(x\) cột \(y\) được gọi là ô \((x, y)\) và có giá trị là \(\begin{cases}1 & \text{nếu}\ \forall k: \lfloor\frac{x}{3^k}\rfloor \text{mod}\ 2 = \lfloor\frac{y}{3^k}\rfloor \text{mod}\ 2\\ 0 & \text{nếu ngược lại}\end{cases}\)

Sau đây là \(9 \times 9\) ô đầu tiên của bảng:

        x
    012345678

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

Có \(Q\) truy vấn có dạng \((d_i, x_i, y_i)\). Với mỗi truy vấn thứ \(i\), bạn cần trả lời tổng các số nằm trên đường chéo \((x_i, y_i), (x_i+1, y_i+1), (x_i+2, y_i+2), \dots, (x_i+d_i, y_i+d_i)\).

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(Q\) \((1 \leq Q \leq 10^4)\)
• \(Q\) dòng tiếp theo, dòng thứ \(i\) lần lượt chứa ba số \(d_i, x_i, y_i\) \((0 \leq x_i, y_i, d_i \leq 10^{18})\)

Định dạng đầu ra

• In ra \(Q\) dòng, dòng thứ \(i\) là đáp án của truy vấn thứ \(i\).

Điểm số

• Test 1 là test ví dụ
• Test 2 thỏa mãn \(d_i \leq 100\) với mỗi truy vấn.
• Test 3-6 thỏa mãn \(x_i+d_i = 3^{30}-1; y=0\) với mỗi truy vấn.
• Test 7-12 không có điều kiện nào khác.

Ví dụ

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