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