kgcd-try1

/*
// Sample code to perform I/O:

cin >> name;                            // Reading input from STDIN
cout << "Hi, " << name << ".\n";        // Writing output to STDOUT

// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
*/

// Write your code here
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll kgcd(ll a, ll b, map<string, ll> &memo);
ll gcd(ll a, ll b, map<string, ll> &memo);

int main(){
    int t;
    scanf("%d", &t);
    //cin >> t;
    //t = 1;
    map<string, ll> memo_gcd;
    map<string, ll> memo_kgcd;
    for(int j = 1; j <= t; j++){
        ll n, count=0;
        ll a, b;
        scanf("%lld", &n);
        //cin >> n;
        //n = 4;

        for(a = 1; a <= n; a++){
            for(b = 1; b <= n; b++){
                //cout << "kgcd(" << a << ", " << b << ") : " << kgcd(a,b) << " | ";
                //cout << "gcd(" << a << ", " << b << ") : " << gcd(a,b, memo) << endl;
                if (kgcd(a,b, memo_kgcd) == gcd(a,b, memo_gcd)){
                    count++;
                }
            }
        }
        //cout << count;
        printf("%lld\n", count);
        /*
        if (j!=t){
            cout << endl;
        }
        */
    }
    return 0;
}

ll kgcd(ll a, ll b, map<string, ll> &memo)
{
    string p = to_string(a) + "," + to_string(b);
    if (memo.find(p) != memo.end()){
        return memo[p];
    }

    while (a > 0 && b > 0)
    {
        a -= b;
        swap(a , b);
    }
    return a + b;
}

ll gcd(ll a, ll b, map<string, ll> &memo){
    if (a > b){
        swap(a, b);
    }
    //pair<ll,ll> p = make_pair(a,b);
    string p = to_string(a) + "," + to_string(b);
    if (memo.find(p) != memo.end()){
        return memo[p];
    }
    while(b){
        a %= b;
        swap(a, b);
    }
    memo[p] = a;
    return a;
}