The Feast

Nafia and Shishir like to feed pets. Today, Nafia has $m$ chocolates and Shishir has $m$ cakes for some cats and dogs. And they are hiring you for a special job.

1. You will choose some cats and distribute some amount of chocolates among them equally such that you have exactly $x$ chocolates left for Nafia.

2. Then, you will choose some dogs (not necessarily equal to the number of cats) and distribute some amount of cakes among them equally such that you have exactly $x$ cakes left for Shishir.

Note that you cannot break any chocolate or cake while distributing.

After that, you will arrange a feast where in each minute, exactly one cat will eat a portion of cake from one dog and that dog will eat a portion of chocolate from that cat simultaneously. The feast will last until every cat eats cake from every dog and every dog eats chocolate from every cat.

Nafia and Shishir want to watch the feast of the cats and dogs and they also want to eat the chocolates and cakes that you have kept for them. So, you have to choose the number of cats and dogs in such a way that both the number of cats and dogs should be greater than $x$ and the feast can continue for at least $m$ minutes. Finally, calculate the minimum duration (in minutes) of the feast.

Input

The first line of the input will consist of an integer, $t$ ${(1 \le t \le 3000)}$$-$ the number of testcases.

Each testcase contains two space separated integers, $m$ and $x$ ${(0 \le x < m \le 10^9 )}$.

Output

For each testcase $-$

• If there is no way to choose such numbers of cats and dogs, print $-1$.

• Otherwise, print an integer denoting the minimum duration of the feast.

Sample

Input	Output
4 15 3 7 5 11 3 24 4	16 -1 16 25
In the first testcase, one possible scenario is you can choose $4$ cats and $4$ dogs and the feast will last for $16$ minutes which is minimum possible duration of the feast under the given condition. In the second testcase, there are no such way to choose number of cats and dogs such that the feast can last at least $7$ minutes.