Remainder Twist
Practice
4.8 (4 votes)
Algorithms
Binary search
Problem
72% Success 1372 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
6 votes
Tags:
Binary SearchAlgorithmsGreedy Algorithms
Points:50
36 votes
Tags:
AlgorithmsApprovedBinary SearchHardOpenSorting
Points:50
7 votes
Tags:
Binary SearchAlgorithmsC++