import java.util.*;  
import java.math.*;  
import java.io.*;


public class Main {  
    public static void main(String[] args) { 
        InputStream inputStream = System.in;  
        OutputStream outputStream = System.out;  
        Scanner in = new Scanner(inputStream);  
        PrintWriter out = new PrintWriter(outputStream);  
        solve(in, out);  
        out.close();  
    }  

    static int ans;
    static int gcd(int a, int b) {
        if(b == 0) return a;
        ans += a / b;
        return b == 0? a : gcd(b, a % b);
    }
    static void solve(Scanner in, PrintWriter out) {  
        int T = in.nextInt();
        while( T -- != 0 ) {
            ans = 0;
            int a = in.nextInt();
            int b = in.nextInt();
            gcd(a, b);
            out.println(ans); out.flush();
        }
    }  
    
    static class Comp implements Comparator {
        public int compare(Object x, Object y) {
            return ((pii) x).X - ((pii) y).X;
        }
    }
    
    static class BIT {
        int maxn;
        int[] tree;
        BIT(int maxn) {
            this.maxn = maxn;
            tree = new int[maxn + 1];
        }
        public int lowbit(int x) {
            return x & -x;
        }
        public int query(int pos) {
            int ans = 0;
            for(int i = pos; i != 0; i -= lowbit(i)) 
                ans = Math.max(ans, tree[i]);
            return ans;
        }
        public void update(int pos, int val) {
            for(int i = pos; i < maxn; i ++) 
                 tree[i] = Math.max(tree[i], val);
        }
        public void clear() {
            for(int i = 0; i < maxn; i ++) tree[i] = 0;
        }
    }
    
    static class pii {
        int X, Y;
        pii(int X, int Y) {
            this.X = X;
            this.Y = Y;
        }
    }

    static class Scanner {    
        BufferedReader br;    
        StringTokenizer st;    
                
        public Scanner(InputStream in) {  
            br = new BufferedReader(new InputStreamReader(in));  
            eat("");  
        }   
          
        private void eat(String s) {    
            st = new StringTokenizer(s);  
        }    
        
        public String nextLine() {    
            try {    
                return br.readLine();    
            } catch (IOException e) {    
                return null;    
            }    
        }    
        
        public boolean hasNext() {    
            while (!st.hasMoreTokens()) {    
                String s = nextLine();    
                if (s == null)    
                return false;    
                eat(s);    
            }    
            return true;    
        }    
        
        public String next() {    
            hasNext();    
            return st.nextToken();    
        }    
        
        public int nextInt() {    
            return Integer.parseInt(next());    
        }    
            
        public long nextLong() {    
            return Long.parseLong(next());    
        }    
                
        public double nextDouble() {    
            return Double.parseDouble(next());    
        }    
            
        public BigInteger nextBigInteger() {    
            return new BigInteger(next());    
        }    
            
            
    }    
}