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.


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})}.


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.


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


Login to submit.


73% Solution Ratio
OnikJahanSagorEarliest, Jul '22
rifatrraazzFastest, 0.0s
rifatrraazzLightest, 17 kB
rifatrraazzShortest, 808B
Toph uses cookies. By continuing you agree to our Cookie Policy.