Троє гномів — Мох, Лист і Корінь — танцюють по колу навколо дуба: за Мохом іде Лист, за Листом — Корінь, а за Коренем — Мох.
Перед танцем кожен гном набирає собі жолудів: Мох бере жолудів, де 1 \le a \le n; Лист бере жолудів, де 1 \le b \le m; Корінь бере жолудів, де 1 \le c \le k.
Кожен гном розкладає свої жолуді на якомога більше купок, у кожній з яких стільки жолудів, скільки їх має наступний гном. Жолуді, що не потрапили в купки, — це залишок гнома. Отже, залишки Моха, Листа і Кореня дорівнюють a \bmod b, b \bmod c і c \bmod a, де x \bmod y — остача від ділення на (наприклад, 7 \bmod 3 = 1, 4 \bmod 11 = 4).
Танець називається гармонійним, якщо залишки всіх трьох гномів однакові:
Для кожного з тестових випадків знайдіть кількість трійок (a, b, c), для яких танець гармонійний.
Перший рядок містить одне ціле число (1 \le t \le 10^5) — кількість тестових випадків.
Кожен з наступних рядків містить три цілі числа , і (1 \le n, m, k \le 10^9).
Для кожного тестового випадку виведіть в окремому рядку одне ціле число — кількість трійок (a, b, c), для яких танець гармонійний.
Приклад 1
У першому тестовому випадку Корінь може взяти лише один жолудь. Єдина підхожа трійка — (1, 1, 1): усі три залишки дорівнюють . Наприклад, трійка (2, 1, 1) не підходить: залишки Моха і Листа дорівнюють , а залишок Кореня — 1 \bmod 2 = 1.