Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
data_dict = {}
k = int(input())
if k == 1:
    print(1)
else:
    ans = 3 * k * k - 3 * k + 1
    for x in range(2, k + 1):
        for y in range(2, k + 1):
            for z in range(2, k + 1):
                if x == y and y == z:
                    ans += x
                elif x == y:
                    if x < z:
                        a = x
                        b = z
                    else:
                        a = z
                        b = x
                    key = str(a) + "-" + str(b)
                    if key in data_dict:
                        ans += data_dict[key]
                    else:
                        d = gcd(a, b)
                        data_dict[key] = d
                        ans += d
                elif y == z:
                    if y < x:
                        a = y
                        b = x
                    else:
                        a = x
                        b = y
                    key = str(a) + "-" + str(b)
                    if key in data_dict:
                        ans += data_dict[key]
                    else:
                        d = gcd(a, b)
                        data_dict[key] = d
                        ans += d
                elif z == x:
                    if z < y:
                        a = z
                        b = y
                    else:
                        a = y
                        b = z
                    key = str(a) + "-" + str(b)
                    if key in data_dict:
                        ans += data_dict[key]
                    else:
                        d = gcd(a, b)
                        data_dict[key] = d
                        ans += d
                else:
                    if x < y:
                        a = x
                        b = y
                    else:
                        a = y
                        b = x
                    key = str(a) + "-" + str(b)
                    if key in data_dict:
                        c = data_dict[key]
                    else:
                        c = gcd(a, b)
                        data_dict[key] = c
                    if c == 1:
                        ans += 1
                    else:
                        if c < z:
                            key = str(c) + "-" + str(z)
                            if key in data_dict:
                                ans += data_dict[key]
                            else:
                                d = gcd(c, z)
                                data_dict[key] = d
                                ans += d
                        else:
                            key = str(z) + "-" + str(c)
                            if key in data_dict:
                                ans += data_dict[key]
                            else:
                                d = gcd(z, c)
                                data_dict[key] = d
                                ans += d
    print(ans)




Fixed submission:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
data_dict = {}
k = int(input())
if k == 1:
    print(1)
else:
    ans = 3 * k * k - 3 * k + 1
    for x in range(2, k - 1):
        for y in range(x + 1, k):
            key = str(x) + "-" + str(y)
            if key in data_dict:
                c = data_dict[key]
            else:
                c = gcd(x, y)
                data_dict[key] = c
            for z in range(y + 1, k + 1):    
                if c == 1:
                    ans += 6
                else:
                    key = str(c) + "-" + str(z)
                    if key in data_dict:
                        ans += data_dict[key] * 6
                    else:
                        d = gcd(c, z)
                        data_dict[key] = d
                        ans += d * 6
    for x in range(2, k):
        for y in range(x + 1, k + 1):
            key = str(x) + "-" + str(y)
            if key in data_dict:
                ans += data_dict[key] * 6
            else:
                d = gcd(x, y)
                data_dict[key] = d
                ans += d * 6
    for x in range(2, k + 1):
        ans += x

    print(ans)