Special Keyboard

Herok, the fastest typist in the world, has a special keyboard. The keyboard only has $n$ 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 $i$ to key at position $j$, he needs $|i-j|$ time, here $|a|$ means the absolute value of $a$. He is so fast that he doesn't require any time to press the key.

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

Input

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

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

The sum of $n$ in all the test cases doesn’t exceed $10^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 $m$ unit of time to type that sequence. If no such sequence exists print $-1$.

Sample

3
5 1
2 5
26 19

1
-1
2