Танок залишків#13070

Танок залишків

1 секунда
256 мегабайтів

Троє гномів — Мох, Лист і Корінь — танцюють по колу навколо дуба: за Мохом іде Лист, за Листом — Корінь, а за Коренем — Мох.

Перед танцем кожен гном набирає собі жолудів: Мох бере жолудів, де 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 \bmod b = b \bmod c = c \bmod a.

Для кожного з тестових випадків знайдіть кількість трійок (a, b, c), для яких танець гармонійний.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^5) — кількість тестових випадків.

Кожен з наступних рядків містить три цілі числа , і (1 \le n, m, k \le 10^9).

Вихідні дані

Для кожного тестового випадку виведіть в окремому рядку одне ціле число — кількість трійок (a, b, c), для яких танець гармонійний.

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку Корінь може взяти лише один жолудь. Єдина підхожа трійка — (1, 1, 1): усі три залишки дорівнюють . Наприклад, трійка (2, 1, 1) не підходить: залишки Моха і Листа дорівнюють , а залишок Кореня — 1 \bmod 2 = 1.