Remainder Twist

★★★★★

4.8

4 votes

, Algorithms, Binary Search

Details

Submissions

Discussion

Editorial

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$

Sample Input

Sample Output

2
3
-1

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$ .

Contributers:

Rohit Pradhan

Tushar Jain