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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class CodeforceSol9a {
	static FastScanner in;
	static PrintWriter out;
	
	public static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in){
			br = new BufferedReader(new InputStreamReader(in));
		}
		
		String next(){
			while (st == null || !st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				} catch (IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt(){
			return Integer.parseInt(next());
		}
		
		long nextLong(){
			return Long.parseLong(next());
		}
		
		double nextDouble(){
			return Double.parseDouble(next());
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		in = new FastScanner(System.in);
		out = new PrintWriter(System.out);
		
		StringBuilder result = new StringBuilder();
		
		int numTests = in.nextInt();
		for(int testNo = 0; testNo < numTests; testNo++){
			int v1 = in.nextInt();
			int v2 = in.nextInt();
			result.append(findOpSub(v1, v2));
			result.append('\n');
		}
		
		out.println(result.toString());
		out.flush();

		out.close();
	
	}

	private static int findOpSub(int v1, int v2) {
		// TODO Auto-generated method stub
		int min = Math.min(v1, v2);
		int max = Math.max(v1, v2);
		
		int result = 0;
		
		while(min > 0 && max > 0){
			result += max / min;
			max = max % min;
			if(min > max){
				int temp = min;
				min = max;
				max = temp;
			}
		}
		
		return result;
	}
	
}
