Корови Фермера Джона розбрелися по величезному пасовищу, представленому у вигляді 2D-гратки (шахової дошки).

Розміщення корів дуже цікаве. Для кожної комірки \((x,y)\) з \(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\) по модулю 3 мають ту саму парність. Тобто обидва ці залишки непарні (рівні \(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

ФД цікавиться скільки корів є у певному квадратному регіоні його пасовища. Він ставить \(Q\) питань, кожен містить три цілих числа \(x_i,y_i,d_i\). Для кожного питання ФД хоче знати, скільки корів у комірках \((x_i,y_i)\) до \((x_i+d_i,y_i+d_i)\) (Включаючи кінцеві точки).

Формат вхідних даних

Перший рядок містить \(Q\) (\(1\le Q\le 10^4\)), кількість питань.

Кожен з наступних \(Q\) рядків містить 3 цілих числа \(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

ОЦІНЮВАННЯ:

• У тесті 2 \(d_i\le 100\) для кожного запиту.
• У тестах 3-6 \(x+d=3^{30}-1\) та \(y=0\) для кожного запиту.
• У тестах 7-12 немає додаткових обмежень.