Functions of the Hell's Kitchen

The District Attorney(DA) of Hell’s Kitchen has been defined following functions.

$GCD(n, m)$: Returns the greatest common divisor of $n$ and $m$.

$SOD(n)$: Returns the sum of distinct positive integer divisors of $n$.

$F(n, k, x)$: Returns the maximum prime divisor of $n$ if any of the following conditions become true and $n$ has at least one prime divisor. Otherwise returns $-n$.

• $GCD(n, k) = n$.

• $SOD(n) - 1 = n$.

• $SOD(n) \ge x$.

Today, Matt Murdock and Wilson Fisk are in a game. Initially $2$ integers ${l, r \ ( l \le r)}$ are given to them. At first, Matt chooses an integer $a$ between $l$ and $r$ inclusively and earns ${F(a, k, x)}$ points. Then, Fisk chooses an integer $b$ between $l$ and $r$ inclusively (not necessarily distinct from $a$) and earns ${F(b, k, x)}$ points. Maximum point earner is the winner.

As Matt is busy saving Hell’s kitchen, he wants you to find an integer $a$ so that at least he doesn’t lose. So, it’s your time to save the savior of Hell’s Kitchen.

Input

First line of the input contains an integer $t$ ${(1 \le t \le 5 \times 10^5)}$ denotes number of testcases.

Each of the testcase contains $4$ space separated integers $l$, $r$ ${(1 \le l \le r \le 10^6)}$, $k$ and $x$ ${(1 \le k, x \le 10^{18})}$.

Output

For each testcase, print any integer $a$ ${(l \le a \le r)}$ so that Matt doesn’t lose at least. If Matt can’t avoid losing, print $-1$.

Sample

Input	Output
4 1 2 1 1 26 79 288 79 7 47 16 30 1 18 35 33	2 79 47 17