Remainder Twist

4.8

4 votes
, Algorithms, Binary Search
Problem

Alice is in love with remainders. His friend Bob gifted her the number \(R\).
A function \(F(X)\) is defined as the number of possible pairs \((A,B)\) such that the following conditions are satisfied:

  • \(A\) and \(B\) are positive integers less than or equal to \(N\).
  • \(A\%B\), the remainder when \(A\) is divided by \(B\), is greater than or equal to \(X\).

Find the maximum possible non-negative integer \(Y\), such that \(F(Y)\) is greater than or equal to \(R\). If it is impossible to find such an integer, print \(-1\).

Input Format

  • The first line contains an integer \(T\), which denotes the number of test cases.
  • The first line of each test case contains two integers, \(N\) and \(R\).

Output Format

For each test case, print \(Y\), the maximum possible non-negative integer such that \(F(Y)\) is greater than or equal to \(R\). If it is impossible to find such an integer, return \(-1\).

Constraints

\(1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 1 \leq R \leq 10^9\)

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case \(1\): If we choose \(Y=2\), then there exist seven pairs of \((A,B)\), i.e. \((4, 5), (2, 5), (3, 5), (2, 4), (3, 4), (2, 3), (5, 3)\). If we choose \(Y=3\), then there exist three pairs, i.e. \((4, 5), (3, 5), (3, 4)\). Therefore the answer will be \(2\).

For test case \(2\):  If we choose \(Y=3\), there exist three pairs, i.e. \((4, 5), (3, 5), (3, 4)\). Therefore the answer will be \(3\).

For test case \(3\): There does not exist any \(Y\) such that \(F(Y)\) is greater than or equal to 26. Therefore the answer will be \(-1\).

Editor Image

?