You are given two integers, a and b. Return the quotient after dividing a by b.
You cannot use the multiplication, division or modulo operator.

Example

a: 15
b: 4
quotient: 3

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input has a line with two space-separated integers a and b.

Output Format

For each test case, the output has one line containing the result.

Sample Input

3
15 4
6 2
15 -4

Expected Output

3
3
-3

Constraints

1 <= T <= 10000
-109 <= a,b <= 109
b != 0