Boss and his Brother
Boss has gone to the market to buy chocolates for his brother. There are total N shops in the market in a linear manner from 1 to N. Boss starts shopping from the 1st shop, then goes to the 2nd shop, then the 3rd and so on. The ith shop has i chocolates. At any shop Boss visits, he buys all the chocolates at that shop.
Now Boss wants to know the minimum number of shops he needs to visit starting from the 1st shop so that he can have at least M chocolates for his brother. Print -1 if he can't have M chocolates even after visiting all the N shops.
The first line of input contains T, denoting the number of test cases. Next T lines will contain N and M as described above.
For each test case, print the required answer in a new line.
- 1 ≤ T ≤ 10^5
- 1 ≤ N,M ≤ 10^18
SubtasksSubtask #1 (20 points), Time limit : 1 sec
1 ≤ T ≤ 10^3, 1 ≤ N,M ≤ 10^6
Subtask #2 (80 points), Time limit : 1 sec
Input: 2 3 2 2 4 Output: 2 -1
In the sample input 1:
for test case 1, Boss will need to visit the first 2 shops for getting at least 2 chocolates.
for test case 2, Boss can get only 3 chocolates even after visiting all the shops. But he needs 4.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions