Вадим работает в научно-исследовательском отделении большой IT-компании. Программировать ему приходится нечасто, а вот изучать самое простое понятие в математике — натуральные числа — приходится каждый день. Как только он не соединял между собой натуральные числа! Вот и сегодня он решил соединить их по-своему.

Два различных числа a, b соединены, если либо a — наибольший не равный b делитель b, либо b — наибольший не равный a делитель a.

Назовём путём последовательность различных натуральных чисел [a₁, a₂, … , a_k] такую, что для всех i из [1, k−1] a_i и a_i+1 соединены и k ≥ 1.

Назовём ценой пути минимальное значение a_i в последовательности.

Теперь Вадиму стало интересно про некоторые пары чисел, существует ли между ними путь и, если он есть, то какой наибольшей цены он может быть.

В первой строке дано единственное число N — количество пар чисел, про которые хочет узнать Вадим (1 ≤ N ≤
5 · 10⁵).

В каждой из следующих N строк через пробел даны по два числа a_i, b_i — очередная пара чисел, про которую хочет узнать Вадим (1 ≤ a_i, b_i ≤ 10⁷).

Выведите N строк. В i-й строке выведите −1, если пути между a_i и b_i нет, иначе выведите единственное целое число — наибольшую цену пути между a_i и b_i.