## GRZZ - zig-zag on the golden river

no tags

Askar is planning to steal some gold from the golden river of Slovakistan! The river forms at (0,0) and flows in the north east direction - the line y = x.

The river is well protected by the king's army, which is sure to give chase after him. As such, he came up with an ingenious plan - he will fly a helicopter, zig-zagging in order to shake off any pursuers. Askar will start at (0,0) and fly dx meters east, then dy meters north, then dx meters east, then dy meters north, ... forever.

Of course, he will only have a small window of opportunity to extract some gold from the river every time he crosses (or touches) it. He has yet to decide the exact values of dx and dy - some might give him better chances at a successful escape, others will allow him to grab more loot.

Help Askar and tell him how much he can get away with for each plan.

### Input

The first line contains an integer 1 ≤ T ≤ 1000 - the number of plans.

T lines follow, each containing two integers 1 ≤ dx, dy ≤ 1015.

### Output

Output a single integer - the number of times Askar would cross the golden river.

If Askar crosses the river an infinite number of times, output -1 instead.

### Example

```Input:
21 13 2

Output:
-11 ```