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 Test5A implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Thread(null, new Test5A(), "", 256 * (1L << 20)).start();
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            if (System.getProperty("ONLINE_JUDGE") != null) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("..\\Codeforces\\src\\com\\congli\\codeforces\\input.txt"));
                out = new PrintWriter(System.out);
            }
            Locale.setDefault(Locale.US);
            solve();
            in.close();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    public String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    public int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    public long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    public double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    // solution

    public void solve() throws IOException 
    {
        int n = readInt();
        int i = 0;
        while(i < n)
        {
            int a = readInt();
            int b = readInt();
            out.println(processLine(a, b));
            ++i;
        }
    }

    private int processLine(int a, int b)
    {
        int count = 0;
        int divide = 0;
        while(a != 0 && b != 0)
        {
            if(a >= b)
            {
                divide = a/b;   
                a %= b;
            }
            else
            {
                divide = b/a;
                b %= a;
            }
            count += divide;
        }
        return count;
    }
}