Functions of the Hell's Kitchen

rifatrraazz RUET CodeSmash 2020
Limits 1s, 512 MB

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

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

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

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

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

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

  • SOD(n)xSOD(n) \ge x.

Today, Matt Murdock and Wilson Fisk are in a game. Initially 22 integers l,r (lr){l, r \ ( l \le r)} are given to them. At first, Matt chooses an integer aa between ll and rr inclusively and earns F(a,k,x){F(a, k, x)} points. Then, Fisk chooses an integer bb between ll and rr inclusively (not necessarily distinct from aa) and earns F(b,k,x){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 aa 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 tt (1t5×105){(1 \le t \le 5 \times 10^5)} denotes number of testcases.

Each of the testcase contains 44 space separated integers ll, rr (1lr106){(1 \le l \le r \le 10^6)}, kk and xx (1k,x1018){(1 \le k, x \le 10^{18})}.

Output

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

Sample

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

Submit

Login to submit.

Statistics

67% Solution Ratio
OnikJahanSagorEarliest, 1M ago
OnikJahanSagorFastest, 0.4s
steinumLightest, 16 MB
steinumShortest, 1122B
Toph uses cookies. By continuing you agree to our Cookie Policy.