Первая строка содержит одно целое число $t$ ($1 \le t \le 1000$)~--- количество наборов входных данных.

В единственной строке каждого набора даны три целых числа $m$, $a$, $c$ ($1 \le m \le 10^{18}$, $1 \le a < c \le 10^6$)~--- значение $\text{rad}(a \cdot b \cdot c)$, длина самого короткого хвоста и длина самого длинного хвоста.
