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 d_x meters east, then d_y meters north, then d_x meters east, then d_y 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 d_x and d_y - 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 ≤ d_x, d_y ≤ 10¹⁵.

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:
2
1 1
3 2

Output:
-1
1