Хвосты тигрокрыса
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Профессор Селезнёв впервые встретился с удивительным зверем тигрокрысом. На лекциях в престижной академии СУНЦ учат, что у этого существа должно быть три хвоста с длинами $$$a$$$, $$$b$$$, $$$c$$$ ($$$a < b < c$$$). Профессор замерил длины $$$a$$$ и $$$c$$$, но вот незадача, средний хвост длины $$$b$$$ куда-то пропал.

Профессор захотел выяснить длину утраченного хвоста, но продавец тигрокрыса покачал головой и вспомнил только лишь число $$$m = \text{rad}(a \cdot b \cdot c)$$$. Напомним, что $$$\text{rad}(n)$$$ это произведение всех различных простых делителей числа $$$n$$$. Например, $$$\text{rad}(504)$$$ = $$$\text{rad}(2^3 \cdot 3^2 \cdot 7) = 2 \cdot 3 \cdot 7 = 42$$$. А также по определению $$$\text{rad}(1) = 1$$$.

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

Входные данные

Первая строка содержит одно целое число $$$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)$$$, длина самого короткого хвоста и длина самого длинного хвоста.

Выходные данные

Для каждого набора входных данных выведите два числа — минимальное и максимальное подходящее $$$b$$$. Если вас обманули и подходящих $$$b$$$ не существует, выведите $$$-1$$$ $$$-1$$$.

Пример

Входные данные

    6210 5 2135 5 7121 11 13870870 14 214520 1 512 2 6

Выходные данные

    6 20-1 -1-1 -129 2088-1 -1-1 -1

Примечание

В первом наборе имеем $$$\text{rad}(a \cdot b \cdot c) = 210 = 2 \cdot 3 \cdot 5 \cdot 7$$$. Минимальное подходящее $$$b = 6$$$: $$$\text{rad}(5 \cdot 6 \cdot 21) = \text{rad}(2 \cdot 3^2 \cdot 5 \cdot 7) = 210$$$. Максимальное подходящее $$$b = 20$$$: $$$\text{rad}(5 \cdot 20 \cdot 21)$$$ = $$$\text{rad}(2^2 \cdot 3 \cdot 5^2 \cdot 7) = 210$$$.