JNJD E

sol.cc

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <queue>

#define fill(v,val) fill((v).begin(), (v).end(), (val))
#define fillt(tab, n, val) fill((t), (t) + (n) ,(val))
#define MAX 100005
#define INF 9999999
#define in(a,b)  ( (b).find(a) != (b).end())
#define clr(a,b) memset((a), (b), sizeof((a)))
#define pb       push_back
#define all(a)   a.begin(), a.end()  
#define mp     make_pair
#define read_fast ios_base::sync_with_stdio(false);
typedef long long ll;

/**
 * @Author Mehdi Maick
 *
 **/
  
using namespace std;
const int mx = 1e5 + 10;

int f(int W, int H){
  if(W == 1) return H;
  if(H == 1) return W;
  if(W == 0 || H == 0) return 0;
  int ans = 1e9;
  if(W < H){
    ans = min(f(H - W, W) + 1, ans); 
  }else{
    ans = min(f(H, W - H) + 1, ans);
  }
  return ans;
}
int main(int argc , char* argv[]) {
  
  int T; cin >> T;
  while(T--){
    int W, H; cin >> W >> H;
    cout << f(W, H) << endl;
  }


  return 0;
}