Vadim works in the research department of a large IT company. He doesn’t have to program often, but he has to study the simplest concept in mathematics — natural numbers — every day. He has connected natural numbers in many ways! Today, he decided to connect them in his own way.

Two different numbers a, b are considered connected if either a is the largest divisor of b that is not equal to b, or b is the largest divisor of a that is not equal to a.

A path is defined as a sequence of distinct natural numbers [a₁, a₂, … , a_k] such that for all i in [1, k−1], a_i and a_i+1 are connected, and k ≥ 1.

The price of a path is the minimum value of a_i in the sequence.

Now Vadim is curious about certain pairs of numbers: whether there is a path between them, and if so, what the maximum price of that path can be.

The first line contains a single integer N — the number of pairs of numbers that Vadim wants to inquire about (1 ≤ N ≤
5 · 10⁵).

Each of the following N lines contains two numbers a_i, b_i separated by a space — the next pair of numbers that Vadim wants to inquire about (1 ≤ a_i, b_i ≤ 10⁷).

Output N lines. In the i-th line, output −1 if there is no path between a_i and b_i; otherwise, output a single integer — the maximum price of the path between a_i and b_i.