source_code: import java.io.*;
  import java.util.*;
  
  public final class Subtractions
  {
      public static void main(String[] args)
      {
          InputReader in = new InputReader(System.in);
          PrintWriter out = new PrintWriter(System.out);
  		Solver solver = new Solver(in, out);
  
  		solver.solve();
          in.close();
          out.flush();
          out.close();
      }
  
      static class Solver
      {
          int n;
          InputReader in;
          PrintWriter out;
  
  		void solve()
  		{
  			n = in.nextInt();
  
  			while (n-- > 0)
  			{
  				int a, b;
  
  				a = in.nextInt();
  				b = in.nextInt();
  
  				int cnt = 0;
  
  				while (a > 0 && b > 0)
  				{
  					if (a < b)
  						a = swap(b, b = a);
  
  					cnt += a / b;
  					a -= b * (a / b);
  				}
  
  				out.println(cnt);
  			}
  		}
  
  		int swap(int a, int b)
  		{
  			return a;
  		}
  
          public Solver(InputReader in, PrintWriter out)
          {
          	this.in = in;
          	this.out = out;
          }
  
  	}
  
      static class InputReader
      {
          private InputStream stream;
          private byte[] buf = new byte[1024];
          private int curChar;
          private int numChars;
  
          public InputReader(InputStream stream)
          {
              this.stream = stream;
          }
  
          public int read()
          {
              if (numChars == -1)
                  throw new InputMismatchException();
  
              if (curChar >= numChars)
              {
                  curChar = 0;
                  try
                  {
                      numChars = stream.read(buf);
                  } catch (IOException e)
                  {
                      throw new InputMismatchException();
                  }
                  if (numChars <= 0)
                      return -1;
              }
  
              return buf[curChar++];
          }
  
          public int nextInt()
          {
              int c = read();
  
              while (isSpaceChar(c))
                  c = read();
  
              int sgn = 1;
  
              if (c == '-')
              {
                  sgn = -1;
                  c = read();
              }
  
              int res = 0;
  
              do
              {
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
  
                  res *= 10;
                  res += c & 15;
  
                  c = read();
              } while (!isSpaceChar(c));
  
              return res * sgn;
          }
  
          public boolean isSpaceChar(int c)
          {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          public void close()
          {
              try
              {
                  stream.close();
              } catch (IOException e)
              {
                  e.printStackTrace();
              }
          }
  
      }
  
  }
  