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

Размещение коров весьма занимательно. Для каждой ячейки (x, y) с x ≥ 0 и y ≥ 0, существует корова в ячейке (x, y) если для всех целых чисел k ≥ 0, остатки ⌊x / 3k⌋ и ⌊y / 3k⌋ по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 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

ФД интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт q вопросов, кажый содержит три целых числа xi, yi, di. Для каждого вопроса ФД хочет знать, сколько коров в ячейках (xi, yi) до (xi + di, yi + di) (включая конечные точки).

Входные данные

Первая строка содержит q (1 ≤ q ≤ 104) - количество вопросов.

Каждая из следующих q строк содержит 3 целых числа di, xi и yi (0 ≤ xi, yi, di ≤ 1018).

Выходные данные

Выведите q строк, по одной для каждого вопроса - одно целое число - ответ.