#include <bits/stdc++.h>

using namespace std;

int gcd(const int a, const int b){
    if(b == 0){
        return a;
    }

    return gcd(b, a % b);
}

pair<int, int> reduce(const int numerator, const int denominator){
    int g = gcd(numerator, denominator);

    int num = numerator / g, denom = denominator / g;

    return {num, denom};
}

// Comparing fractions without the need of actually dividing
bool sorter(const pair<int, int>& a, const pair<int, int>& b){
    return a.first * b.second < b.first * a.second;
}

int main(){

    cout << "Hello this is Patrick" << endl;
    auto start = chrono::high_resolution_clock::now();

    set<pair<int, int>> fraction_set;
    vector<pair<int,  int>> fraction_list;

    for(int i = 1; i <= 12000; ++i){
        for(int j = 1; j < i; ++j){
            auto fraction = reduce(j, i);
            fraction_set.insert(fraction);
        }
    }

    for(auto frac : fraction_set){
        fraction_list.push_back(frac);
    }

    sort(fraction_list.begin(), fraction_list.end(), sorter);

    int counter = 0;
    bool counting = false;

    for(auto frac : fraction_list){
        if(counting){
            counter++;
        }

        if(frac.first == 1 && frac.second == 3){
            counting = true;
        } else if(frac.first == 1 && frac.second == 2){
            break;
        }
    }

    cout << counter - 1 << endl;

    auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start);
    cout << (float)duration.count()/1000 << endl;
    return 0;
}