Підрахунок корів
Корови Фермера Джона мешкають на величезному полі, яке має вигляд шахової решітки.
Цікаво, що ці корови розміщені саме в тих місцях, де їх не очікуєш. Для кожної комірки (x, y) на цьому полі, якщо розглядати цю комірку як частину числа, то вона має бути в певному діsпаді. Наприкод, якщо розглянути всі комірки, які знаходяться в межах 0 ≤ x, y < 9, то вони будуть виглядати так:
x 012345678 y 0 101000101 1 010000010 2 101000101 3 000101000 4 000010000 5 000101000 6 101000101 7 010000010 8 101000101
Це означає, що для кожної комірки (x, y) з координатами x та y, що відповідають певним умовам, корова буде присутня. Ці умови включають в себе те, що залишки, які ми розглядаємо, мають бути парними або непарними.
Фермер Джон хоче знити, скілько корів знаходиться в певному квадратному регіоні, який він визначає. Він задає q запитів, кожен з яких містить три числа: x, y та d. Для кожного запиту він хоче знити, скіло корів знаходиться в цьому регіні.
Вхідні дани
Перша рядка містить число q (1 ≤ q ≤ 10^4) - кілька запитів.
Кожний з наступних q рядків містить три числа: x, y та d (0 ≤ x, y, d ≤ 10^18).
Вихідні дани
Для кожного запиту виведіть одне ціло число, яке відповідає кільку корів у цьому регіні.