there are N contest and you have decided to distribute X T-shirts in each contest for winners. The number of T-shirts that must be distributed in each contest must be equal. As you are the organizer of this sores, you also need a T-shirt. You must order these T-shirts as soon as possible but your vendor takes orders in packs of T-shirts where each pack consists of M T-shirts. You are required to order the minimum numbers of packs that satisfy the mentioned conditions.

Output format

For each test case, print the least number of packs that are required to fulfil the conditions. If it is not possible to satisfy the criteria of ordering T-shirts, then print -1. The answer for each test case should come in a new line.

Constraints

1< T <100000

1 < N, M < 100000

sample input

2

3 4

10 7

Output

1

3

Explaination

1st Test Case : N=3 m=4 so if you buy a single pack of T - shirts It will fullfill the requirement you can gave 3 Tshirt to topper of the each contest a. kept one for yourself. 3+1 = 4

2nd Test Case N=10 M=7 so If you buy 3 packs of T-shirt will fullfill the requirements with minimum order. You can gave 2 T-shirt to top Performer of each contests and kept one for yourself . 2•10+1 = 20+1= 21(3 packs )