Qalıqların rəqsi#13070

Qalıqların rəqsi

1 saniyə
256 meqabayt

Üç cırtdan — Mamır, Yarpaq və Kök — palıd ağacının ətrafında dövrə vuraraq rəqs edirlər: Mamırın ardınca Yarpaq, Yarpağın ardınca Kök, Kökün ardınca isə Mamır gedir.

Rəqsdən əvvəl hər cırtdan özü üçün bir qədər palıd qozası yığır: Mamır qoza götürür, burada 1 \le a \le n; Yarpaq qoza götürür, burada 1 \le b \le m; Kök qoza götürür, burada 1 \le c \le k.

Hər cırtdan öz qozalarını mümkün qədər çox topaya düzür və hər topada növbəti cırtdanın qozalarının sayı qədər qoza olur. Topalara sığmayan qozalar həmin cırtdanın qalığıdır. Beləliklə, Mamırın, Yarpağın və Kökün qalıqları uyğun olaraq a \bmod b, b \bmod c və c \bmod a qiymətlərinə bərabərdir, burada x \bmod y — ədədinin ədədinə bölünməsindən alınan qalıqdır (məsələn, 7 \bmod 3 = 1, 4 \bmod 11 = 4).

Əgər hər üç cırtdanın qalıqları bərabərdirsə, rəqs harmonik adlanır:

a \bmod b = b \bmod c = c \bmod a.

test halının hər biri üçün rəqsin harmonik olduğu (a, b, c) üçlüklərinin sayını tapın.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 10^5) — test hallarının sayı verilir.

Sonrakı sətrin hər birində üç tam ədəd , və (1 \le n, m, k \le 10^9) verilir.

Çıxış

Hər test halı üçün ayrıca sətirdə bir tam ədəd — rəqsin harmonik olduğu (a, b, c) üçlüklərinin sayını çıxarın.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci test halında Kök yalnız bir qoza götürə bilər. Yeganə uyğun üçlük (1, 1, 1)-dir: hər üç qalıq -a bərabərdir. Məsələn, (2, 1, 1) üçlüyü uyğun deyil: Mamırın və Yarpağın qalıqları , Kökün qalığı isə 1 \bmod 2 = 1-dir.