eolymp
bolt
Try our new interface for solving problems
Məsələlər

Разбиение треугольника

Разбиение треугольника

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Треугольник можно разбить на два треугольника, проведя медиану к его большей стороне (на рисунке сверху такое разбиение показано красным разрезом). Затем два меньших треугольника можно подобным образом разделить на четыре треугольника (на рисунке такое разбиение показано синими разрезами). Процесс разрезания треугольников будем продолжать до бесконечности.

Математики заметили, что при описанном разрезании мы получим конечное количество "стилей" треугольников, которые отличаются друг от друга только размером. По заданным длинам сторон исходного треугольника необходимо определить количество стилей треугольников, которое можно получить. Два треугольника принадлежат одному стилю, если они подобны.

Giriş verilənləri

Первая строка содержит количество тестов n (0 < n < 35). Каждая следующая строка содержит три целых числа a, b, c (0 < a, b, c < 100) - стороны треугольника. Известно, что площадь каждого входного треугольника положительна.

Çıxış verilənləri

Для каждого теста в отдельной строке вывести его номер как показано в примере и целое число t - количество разных стилей треугольников, которое получится в процессе указанного деления. Считать, что значение t всегда меньше 100.

Nümunə

Giriş verilənləri #1
2
3 4 5
12 84 90
Çıxış verilənləri #1
Triangle 1: 3
Triangle 2: 41