You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (*a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>). How many operations will be performed for each of them?
The first line contains the number of pairs *n* (1  ≤  *n*  ≤  1000). Then follow *n* lines, each line contains a pair of positive integers *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1  ≤  *a*<sub class="lower-index">*i*</sub>,  *b*<sub class="lower-index">*i*</sub>  ≤  10<sup class="upper-index">9</sup>).
n = int(input())

for i in range(n):
    (a, b) = map(int, input().split(' '))
    if a == b:
        print(1)
    else:
        operations = 0
        bigger_number = max(a, b)
        smaller_number = min(a, b)
        while bigger_number != smaller_number:
            if bigger_number % smaller_number == 0:
                operations += smaller_number
                bigger_number = (bigger_number - smaller_number) // smaller_number
            else:
                operations += bigger_number // smaller_number
                bigger_number = bigger_number % smaller_number

            if bigger_number < smaller_number:
                smaller_number, bigger_number = bigger_number, smaller_number

        print(operations + 1)
