Special Keyboard

curly_braces Criterion 2022 Round 19
Limits 1s, 512 MB

Herok, the fastest typist in the world, has a special keyboard. The keyboard only has nn different keys each representing a different character. All the keys are on a single line. The first key at the leftmost position, the second one at the second from left position, and so on. As it’s a one-line keyboard, he can type with two fingers only, otherwise, it gets too complicated.

Herok starts with one of his two usable fingers at the leftmost key and the other one at the rightmost key. He types out a sequence of characters one by one, starting from the first character. To type a character, if there is a finger positioned at the corresponding key, Herok immediately presses the key to type the character, otherwise, he moves one of his fingers to the key and then presses the key. On deciding which finger to move, he always chooses the one that’s closest to the key, if both of the fingers are at the same distance, he always chooses the left finger. To move a finger from key at position ii to key at position jj, he needs ij|i-j| time, here a|a| means the absolute value of aa. He is so fast that he doesn't require any time to press the key.

Herok wonders for some value m,(1m109)m,(1 \leq m \leq 10^9), what is the minimum possible length of the character sequence for which he will need exactly mm unit of time to type that sequence. Can you help him?

Input

Input starts with T(1T105)T(1 \leq T \leq 10^5), the number of testcases.

The next TT lines contain two integers each, n,m(2n106,1m109)n, m (2 \leq n \leq 10^{6}, 1 \leq m \leq 10^9), described above.

The sum of nn in all the test cases doesn’t exceed 10610^6.

Output

For each test case, in one line print an integer, the minimum possible length of the character sequence for which he will need exactly mm unit of time to type that sequence. If no such sequence exists print 1-1.

Sample

InputOutput
3
5 1
2 5
26 19
1
-1
2

Submit

Login to submit.

Statistics

22% Solution Ratio
rkb_rdEarliest, 3w ago
ash_98Fastest, 0.0s
murad928Lightest, 3.0 kB
murad928Shortest, 299B
Toph uses cookies. By continuing you agree to our Cookie Policy.