#include <iostream>
#include <vector>
#include <utility>
using namespace std;

unsigned gcd(unsigned a, unsigned b, unsigned * const cost) {
  if (cost) {
    *cost = 0;
  }
  while (b != 0) {
    auto const rest = a % b;
    if (cost) {
      ++(*cost);
    }
    a = b;
    b = rest;
  }
  return a;
}


int main() {
  unsigned const n = 3500;
  unsigned greatestCost = 0;
  vector<pair<unsigned, unsigned>> pairs;
  for (unsigned b = 8; b <= n; ++b) {
    for (unsigned a = 0; a <= b; ++a) {
      unsigned cost;
      gcd(a, b, &cost);
      if (cost == greatestCost) {
        pairs.emplace_back(a, b);
      } else if (cost > greatestCost) {
        pairs.clear();
        pairs.emplace_back(a, b);
        greatestCost = cost;
      }
    }
  }
  cout << "Greatest cost is " << greatestCost << " when calculating the GCD of " << endl;
  for (auto const & p : pairs) {
    cout << "(" << p.first << ", " << p.second  << ")" << endl;
  }
  return 0;
}