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 (ai, bi). How many operations will be performed for each of them?

Input

The first line contains the number of pairs n (1 ≤ n ≤ 1000). Then follow n lines, each line contains a pair of positive integers ai, bi (1 ≤ ai, bi ≤ 109).

Output

Print the sought number of operations for each pair on a single line.

Examples

Input

2
4 17
7 987654321


Output

8
141093479
import java.io.*;
import java.util.*;

public class CodeForces8 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numPairs = sc.nextInt();
        sc.nextLine();
        // run through each pair of numbers
        for (int pair = 0; pair < numPairs; pair++) {
            // get each number
            int hi = sc.nextInt();
            int low = sc.nextInt();
            // check for existence of another line
            if (sc.hasNextLine()) {
                sc.nextLine();
            }
            // check hi and low assigned correctly
            if (hi < low) {
                int temp = hi;
                hi = low;
                low = temp;
            }
            // now time to calculate
            operations(hi, low);
        }
    }

    // method to print out operations
    public static void operations(int hi, int low) {
        int numOps = 0;
        // go through operations
        while (hi > 0 && low > 0) {
            // check if hi and low are equal to each other
            if (hi == low) {
                // subtract one from other, no more ops
                hi -= low;
                numOps++;
            } else {
                // not equal, do normal ops
                int subOps = hi / low;
                numOps += subOps;
                // take subOps away from hi
                hi = hi % low;
                // check if hi and low values swapped
                if (hi < low) {
                    int temp = hi;
                    hi = low;
                    low = temp;
                }
            }
        }
        // counted all ops
        System.out.println(numOps);
    }
}