Problem:
 Score : 300 points    Problem Statement Find \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)} .  Here \gcd(a,b,c) denotes the greatest common divisor of a , b , and c .      Constraints  1 \leq K \leq 200  K is an integer.         Input Input is given from Standard Input in the following format:  K       Output Print the value of \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)} .        Sample Input 1 2      Sample Output 1 9  \gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)  +\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)  =1+1+1+1+1+1+1+2=9  Thus, the answer is 9 .       Sample Input 2 200      Sample Output 2 10813692

Solution (Python):
from collections import Counter


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def gcd_3(a, b, c, mem):
    a_p = prime_factors(a) if a not in mem.keys() else mem[a]
    b_p = prime_factors(b) if b not in mem.keys() else mem[b]
    c_p = prime_factors(c) if c not in mem.keys() else mem[c]

    if a not in mem.keys():
        mem[a] = a_p
    if b not in mem.keys():
        mem[b] = b_p
    if c not in mem.keys():
        mem[c] = c_p

    a_f = Counter(a_p)
    b_f = Counter(b_p)
    c_f = Counter(c_p)
    common_factors = [(k, min([a_f[k], b_f[k], c_f[k]])) for k in a_f.keys() if k in b_f.keys() and k in c_f.keys()]
    common_factors = [[k] * v for k, v in common_factors]
    common_factors = [k for sublist in common_factors for k in sublist]

    res = 1

    for n in common_factors:
        res *= n

    return res


def solve(k, mem, mem_1):
    res = 0
    for i in range(1, k + 1):
        for j in range(1, k + 1):
            for h in range(1, k + 1):
                key = tuple(sorted([i, j, h]))
                if key in mem_1:
                    res += mem_1[key]
                else:
                    curr = gcd_3(i, j, h, mem)
                    res += curr
                    mem[key] = curr
    return res


prerecorded = {
    1: 1,
    2: 9,
    3: 30,
    4: 76,
    5: 141,
    6: 267,
    7: 400,
    8: 624,
    9: 885,
    10: 1249,
    11: 1590,
    12: 2208,
    13: 2689,
    14: 3411,
    15: 4248,
    16: 5248,
    17: 6081,
    18: 7485,
    19: 8530,
    20: 10248,
    21: 11889,
    22: 13687,
    23: 15228,
    24: 17988,
    25: 20053,
    26: 22569,
    27: 25242,
    28: 28588,
    29: 31053,
    30: 35463,
    31: 38284,
    32: 42540,
    33: 46581,
    34: 50893,
    35: 55362,
    36: 61824,
    37: 65857,
    38: 71247,
    39: 76884,
    40: 84388,
    41: 89349,
    42: 97881,
    43: 103342,
    44: 111528,
    45: 120141,
    46: 128047,
    47: 134580,
    48: 146316,
    49: 154177,
    50: 164817,
    51: 174438,
    52: 185836,
    53: 194157,
    54: 207927,
    55: 218812,
    56: 233268,
    57: 245277,
    58: 257857,
    59: 268182,
    60: 288216,
    61: 299257,
    62: 313635,
    63: 330204,
    64: 347836,
    65: 362973,
    66: 383709,
    67: 397042,
    68: 416448,
    69: 434025,
    70: 456967,
    71: 471948,
    72: 499740,
    73: 515581,
    74: 536073,
    75: 559758,
    76: 583960,
    77: 604833,
    78: 633651,
    79: 652216,
    80: 683712,
    81: 709065,
    82: 734233,
    83: 754734,
    84: 793188,
    85: 818917,
    86: 846603,
    87: 874512,
    88: 909496,
    89: 933081,
    90: 977145,
    91: 1006126,
    92: 1041504,
    93: 1073385,
    94: 1106467,
    95: 1138536,
    96: 1187112,
    97: 1215145,
    98: 1255101,
    99: 1295142,
    100: 1342852,
    101: 1373253,
    102: 1422195,
    103: 1453816,
    104: 1502376,
    105: 1553361,
    106: 1595437,
    107: 1629570,
    108: 1691292,
    109: 1726717,
    110: 1782111,
    111: 1827492,
    112: 1887772,
    113: 1925853,
    114: 1986837,
    115: 2033674,
    116: 2089776,
    117: 2145333,
    118: 2197483,
    119: 2246640,
    120: 2332104,
    121: 2379085,
    122: 2434833,
    123: 2490534,
    124: 2554600,
    125: 2609625,
    126: 2693919,
    127: 2742052,
    128: 2813988,
    129: 2875245,
    130: 2952085,
    131: 3003306,
    132: 3096024,
    133: 3157249,
    134: 3224511,
    135: 3306240,
    136: 3388576,
    137: 3444609,
    138: 3533637,
    139: 3591322,
    140: 3693924,
    141: 3767085,
    142: 3842623,
    143: 3912324,
    144: 4027884,
    145: 4102093,
    146: 4181949,
    147: 4270422,
    148: 4361548,
    149: 4427853,
    150: 4548003,
    151: 4616104,
    152: 4718640,
    153: 4812789,
    154: 4918561,
    155: 5003286,
    156: 5131848,
    157: 5205481,
    158: 5299011,
    159: 5392008,
    160: 5521384,
    161: 5610705,
    162: 5739009,
    163: 5818390,
    164: 5930196,
    165: 6052893,
    166: 6156139,
    167: 6239472,
    168: 6402720,
    169: 6493681,
    170: 6623853,
    171: 6741078,
    172: 6864016,
    173: 6953457,
    174: 7094451,
    175: 7215016,
    176: 7359936,
    177: 7475145,
    178: 7593865,
    179: 7689630,
    180: 7886244,
    181: 7984165,
    182: 8130747,
    183: 8253888,
    184: 8403448,
    185: 8523897,
    186: 8684853,
    187: 8802826,
    188: 8949612,
    189: 9105537,
    190: 9267595,
    191: 9376656,
    192: 9574704,
    193: 9686065,
    194: 9827097,
    195: 9997134,
    196: 10174780,
    197: 10290813,
    198: 10493367,
    199: 10611772,
    200: 10813692
}

if __name__ == '__main__':
    k = int(input())

    print(prerecorded[k])

Solution (Python):
import math
k=int(input())
s=0
for p in range(k):
  for q in range(k):
    g=math.gcd(p+1,q+1)
    for i in range(k):
      r=math.gcd(g,i+1)
      s=s+r
print(s)

Solution (Python):
import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            if (i == j == k):
                ans += i
            if(i == j and j!= k ):
                    ans += 3*math.gcd(k,math.gcd(i,j))
            if(i<j<k and i != j != k):
                    ans += 6*math.gcd(k,math.gcd(i,j))

print(ans)

Solution (Python):
import math
K = int(input())
num_list = []

for t in range(K):
  a = t + 1
  for s in range(K):
    b = s + 1
    koyaku = math.gcd(a,b)
    for u in range(K):
      c = u + 1
      num_list.append(math.gcd(koyaku,c))
      
print(sum(num_list))

Solution (Python):

import math


k = int(input())
sum = 0.0

for a in range(1, k+1):
    for b in range(1, k+1):
        gcd_ab = math.gcd(a, b)
        for c in range(1, k+1):
            sum = sum + math.gcd(gcd_ab, c)

print(int(sum))

Solution (Python):
import math
 
K = input()
 
Sum = 0
k = int(K)
 
for A in range(k):
    a = A + 1
    for B in range(k):
        b = B + 1
        gcd_ab = math.gcd(a, b)
        for C in range(k):
            c = C + 1
 
            Sum = Sum + math.gcd(gcd_ab, c)
 
print(Sum)

Solution (Python):
import math
import itertools

k = int(input())
l = range(1, k+1)

cnt = sum(l)
two = list(itertools.combinations(l, 2))
for li in two:
    gcd = 1 if 1 in li else math.gcd(li[0], li[1])
    cnt += gcd*6

if k > 2:
    three = list(itertools.combinations(l, 3))
    for li in three:
        gcd = 1 if 1 in li else math.gcd(math.gcd(li[0], li[1]), li[2])
        cnt += gcd*6

print(cnt)

Solution (Python):
n = int(input())
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
total = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            total += gcd(i+1,gcd(j+1,k+1))
print(total)

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

K = int(input())
mod = 10**9 + 7

N = 3

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 0

M = np.zeros(K+1, dtype=int)

for i in range(K, 0, -1):

    M[i] += pow(K//i, N)
    
    for j in range(2,K//i+1):
        j *= i
        M[i] -= M[j]
    
    ans += M[i] * i
    
        
print(ans)

Solution (Python):
import itertools
import math

K = int(input())
nums = [i for i in range(1, K+1)]
product = itertools.product(nums, repeat=3)
ans = 0
for comb in product:
    m = min(comb)
    if m == 1:
        ans += m
    else:
        for i in range(0, 3):
            m = math.gcd(m, comb[i])
        ans += m
print(ans)

Solution (Python):
import math
def gcd3(a, b, c):
    return math.gcd(math.gcd(a,b), c)

k = int(input())
sum = 0
for a in range(k):
    if a == 0:
        sum += k * k
        continue
    else:
        for b in range(k):
            if b == 0:
                sum += k
                continue
            else:
                for c in range(k):
                    if c == 0:
                        sum += 1
                    else:
                        sum += gcd3(a+1,b+1,c+1)
print(sum)

Solution (Python):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())

ans = 0
for i in range(1, k+1):
  for j in range(1, k+1):
    for k in range(1, k+1):
      ans += gcd(i, j, k)
print(ans)

Solution (Python):
def gcd2(a,b):
    x, y = max(a, b), min(a, b)
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            x, y = y, x % y
        return y


K = int(input())
s = [gcd2(a, b) for a in range(1, K+1) for b in range(a+1, K+1)]
t = [2 * gcd2(a, b) for a in range(1, K+1) for b in s]
n = [gcd2(a, b) for a in range(1, K+1) for b in range(1, K+1)]
print(sum(t)+sum(n))

Solution (Python):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(i,k+1):
        for p in range(j,k+1):
            if (i!=j) and (j!=p) and (i!=p):
                
                ans += gcd(i,j,p) * 6
            elif (i==j) and (j==p):
                
                ans += gcd(i,j,p)
            else:
                
                
                ans += gcd(i,j,p) * 3

print(ans)

Solution (Python):
from math import gcd

k = int(input())

ans = 0

for a in range(1, k+1):

    for b in range(1, k+1):

        for c in range(1, k+1):

            ans += gcd(gcd(a, b), c)

print(ans)

Solution (Python):
from math import gcd

K = int(input())

ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
          ans += gcd(gcd(i, j), k)

print(ans)

Solution (Python):
import numpy as np
import sys
import math



data = [2246640
,2332104
,2379085
,2434833
,2490534
,2554600
,2609625
,2693919
,2742052
,2813988
,2875245
,2952085
,3003306
,3096024
,3157249
,3224511
,3306240
,3388576
,3444609
,3533637
,3591322
,3693924
,3767085
,3842623
,3912324
,4027884
,4102093
,4181949
,4270422
,4361548
,4427853
,4548003
,4616104
,4718640
,4812789
,4918561
,5003286
,5131848
,5205481
,5299011
,5392008
,5521384
,5610705
,5739009
,5818390
,5930196
,6052893
,6156139
,6239472
,6402720
,6493681
,6623853
,6741078
,6864016
,6953457
,7094451
,7215016
,7359936
,7475145
,7593865
,7689630
,7886244
,7984165
,8130747
,8253888
,8403448
,8523897
,8684853
,8802826
,8949612
,9105537
,9267595
,9376656
,9574704
,9686065
,9827097
,9997134
,10174780
,10290813
,10493367
,10611772
,10813692]


k = int(input())

if k >= 119:
    print(data[k-119])
    sys.exit()


def gcd(a,b):
    if a > b:
        a , b = b , a

    
    r = b % a

    if r == 0:
        return a
    else:
        return gcd(a,r)
    

sum = 0



for i in range(k):
    for j in range(k):
        for l in range(k):
            sum += gcd(i+1,gcd(j+1,l+1))


print(sum)

Solution (Python):
import math
k= int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        x = math.gcd(a,b)
        for c in range(1,k+1):
            ans += math.gcd(x,c)
print(ans)

Solution (Python):
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
k=int(input())
ans=0
first=k*(k+1)//2
second=0

for i in range(1,k):
    for j in range(i+1,k+1):
        second+=gcd(i,j)*6

thir=0
for i in range(1,k-1):
    for j in range(i+1,k):
        for h in range(j+1,k+1):
            tmp=gcd(gcd(i,j),h)
            thir+=tmp*6

if k==1:
    print(first)
elif k==2:
    print(first+second)
else:
    print(first+second+thir)

Solution (Python):

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
s = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            i = gcd(a,b,c)
            s += i
print(s)

Solution (Python):
from math import gcd
N = int(input())

ans = 0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            ans += gcd(gcd(a, b), c)
print(ans)

Solution (Python):
from math import gcd
K = int(input())
total = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            total += gcd(gcd(a, b), c)
print(total)

Solution (Python):
import math
from functools import reduce

k = int(input())
a = 0

for i in range(1, k + 1):
    for l in range(1, k + 1):
        for m in range(1, k + 1):
            a += reduce(math.gcd, [i, l, m])
print(a)

Solution (Python):
import math
from functools import reduce

def gcd(*nums):
  return reduce(math.gcd, nums)


input_num = int(input()) + 1
result = 0
for a in range(1, input_num):
  for b in range(1, input_num):
    for c in range(1, input_num):
        result += gcd(a, b, c)

print(result)

Solution (Python):

import sys
import math
input = sys.stdin.readline


def main():
    k = int(input())
    result = 0

    memory = [[0 for j in range(k)] for i in range(k)]
    for i in range(1, k + 1):
        for j in range(i, k + 1):
            gcd = math.gcd(i, j)
            memory[i-1][j-1] = gcd
            memory[j-1][i-1] = gcd

    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                result += memory[a-1][memory[b-1][c-1]-1]

    print(result)


if __name__ == '__main__':
    main()

Solution (Python):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input()) + 1
cache = []

for i in range(1, K):
    for j in range(i, K):
        if (i == j):
            continue
        else:
            cache.append(gcd(i, j))


sum = 0
for j in range(1, K):
    for i in range(len(cache)):
        if (cache[i] == 1 or j == 1):
            sum += 1 * 2
        else:
            sum += gcd(cache[i], j) * 2
    for k in range(1, K):
        sum += gcd(j, k)

print(sum)

Solution (Python):
import math
from functools import reduce

k=int(input())
sum = 0

for a in range(k+1):
    for b in range(k+1):
        tmp = math.gcd(a,b)
        for c in range(k+1):
            if a != 0 and b != 0 and c != 0:
                sum = sum + math.gcd(tmp,c)

print(sum)

Solution (Python):
import math
n = int(input())
num = 0
tmp = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        tmp = math.gcd(i,j) 
        for k in range(1,n+1):
            num += math.gcd(tmp, k)
            tmp == 0
print(num)

Solution (Python):
import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


ans = 0
K = int(input())
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(a, b, c)

print(ans)

Solution (Python):
from math import gcd
K = int(input())
total = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += gcd(a, gcd(b, c))

print(total)

Solution (Python):

"""
Created on Sun Apr 12 22:01:05 2020

@author: H_Hoshigi
"""

import math

K = int(input())
answer = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        gcd_a_b = math.gcd(a, b)
        for c in range(1, K+1):
            answer += math.gcd(gcd_a_b, c)
print(answer)

Solution (Python):
import math
from functools import reduce
 
def aaa(*numbers):
    return reduce(math.gcd, numbers)
 
num = int(input())
list = []
for i in range(1,num+1):
    for j in range(1,num+1):
        for k in range(1,num+1):
            list.append(aaa(i,j,k))
print(sum(list))

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
K=int(input())


z=0
dic=defaultdict(int)
for a in range(1,K+1):
    for b in range(1,K+1):
        d=gcd(a,b)
        dic[d]+=1
for d in dic:

    for c in range(1,K+1):
        z+=dic[d]*gcd(c,d)
print(z)

Solution (Python):
import math
K = int(input())

temp_list = []
temp_list_2 = []
for i in range(1, K+1):
    for j in range(1, K+1):
        temp_list.append(math.gcd(i, j))
for i in range(1, K+1):
    for j in temp_list:
        temp_list_2.append(math.gcd(i, j))
print(sum(temp_list_2))

Solution (Python):
import sys
input = sys.stdin.readline
import math 

X = int(input())
s = 0

for i in range(1,X+1):
   for j in range(1,X+1):
      ij = math.gcd(i,j)
      for k in range(1,X+1):
        s = s + math.gcd(ij,k)

print (s)

Solution (Python):
a=int(input())
Number=[l for l in range(a+1)]
Number.pop(0)
List=[]
import math
for i in Number:
    for j in Number:
        b=math.gcd(i,j)
        for  k in Number:
            c=math.gcd(b,k)
            List.append(c)
print(sum(List))

Solution (Python):
import math
from functools import reduce

k = int(input())

ans = 0
for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            temp = reduce(math.gcd,[i,j,l])
            if len(set([i,j,l])) == 1:
                ans += temp
            elif len(set([i,j,l])) == 2:
                ans += temp * 3
            elif len(set([i,j,l])) == 3:
                ans += temp * 6
print(ans)

Solution (Python):


import itertools
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
lis = list(itertools.combinations_with_replacement(range(1, K+1), 3))

ans=0
for i, j, k in lis:
    if i==j and j==k and i==k:
        ans+=gcd(i, j, k)
    elif i!=j and j!=k and i!=k:
        ans+=6*gcd(i, j, k)
    else:
        ans+=3*gcd(i, j, k)

print(ans)

Solution (Python):
import math

k=int(input())


sum=0
for i in range(k):
    for j in range(k):
        for l in range(k):
            sum+=math.gcd(math.gcd(i+1,j+1),l+1)

print(sum)

Solution (Python):
import fractions as f

n = int(input())   
l = [[0 for i in range(n+1)] for j in range(n+1)]


cnt =0
for a in range(1,n+1):
    for b in range(1,n+1):
        
        if a > b : 
            q, w = b, a
        else:
            q ,w = a, b

        x = l[q][w]

        if x == 0:
            x = f.gcd(q, w)
            
            l[q][w] = x
        
        
            
        for c in range(1,n+1):
            e = x
            
            
            if e > c : e, c = c, e

            y = l[e][c]
            if y == 0:
                y = f.gcd(e, c)
                
                l[e][c] = y

            cnt += y
            

print (cnt)

Solution (Python):
from math import gcd
from itertools import combinations_with_replacement as cwr

K = int(input())
n = range(1, K+1)
total = 0

for a,b,c in cwr(n,3):
    d = gcd(gcd(a,b),c)
    if a == b == c:
        total += d
    elif a != b != c:
        total += d*6
    else:
        total += d*3

print(total)

Solution (Python):
import math
k=int(input())
s=0

for i in range(k):
  for j in range(k):
    for l in range(k):
      c=math.gcd(i+1,j+1)
      s+=math.gcd(c,l+1)
      
print(s)

Solution (Python):

import re
import math
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)


import re
import math
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)

@lru_cache(maxsize=None)
def f(a,b):
    return math.gcd(a,b)
K=int(input())
ans=0
gc=[]
for a in range(1,K+1):
    for b in range(1,K+1):
        gc.append(f(a,b))
for a in range(1,K+1):
    for b in gc:
        ans+=f(a,b)
print(ans)

Solution (Python):
k = int(input())
 
import math
total = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        gcd2 = math.gcd(a, b)
        for c in range(1, k+1):
            total += math.gcd(gcd2, c)
print(total)

Solution (Python):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

k = int(input())
num = k+2
lst = [([None]*num) for i in range(num)]

for i in range(num):
    for j in range(num):
        lst[i][j] = gcd(i+1,j+1)


ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        NUM = lst[a-1][b-1]
        for c in range(1,k+1):
            ans += lst[NUM-1][c-1]

print(ans)

Solution (Python):
from functools import lru_cache

N = int(input())

@lru_cache(maxsize=None)
def gcd2(a, b):
  while b != 0:
    a, b = b, a % b
  return a

def gcd(a, b, c):
  return gcd2(gcd2(a, b), c)

res = 0

for i in range(1, N + 1):
  for j in range(i, N + 1):
    for k in range(j, N + 1):
      if i == j == k:
        res += gcd(k, j, i)
      elif i != j != k:
        res += gcd(k, j, i) * 6
      else:
        res += gcd(k, j, i) * 3

print(res)

Solution (Python):
from math import gcd

k = int(input())


ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)

Solution (Python):
def gcd(a, b):
  if a%b == 0:
    return(b)
  else:
    return(gcd(b, a%b))

def gcd3(a,b,c):
  d = gcd(a,b)
  ans = gcd(d,c)
  return ans

def main():
  K = int(input())

  ans = 0

  for i in range(K):
    for j in range(K):
      for k in range(K):
        ans += gcd3(i+1,j+1,k+1)

  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
from math import  gcd

k = int(input())
out = 0


out = out + (1 + k) * k / 2


for i in range(k):
    a = i + 1
    b = i + 1
    for j in range(a - 1):
        c = j + 1
        out = out + gcd(a, c) * 6


for m in range(k):
    a = m + 1
    for n in range(a - 1):
        b = n + 1
        gcd2 = gcd(a, b)
        for o in range(b - 1):
            c = o + 1
            out = out + gcd(gcd2, c) * 6


print(int(out))

Solution (Python):
from math import gcd

k = int(input())


ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)

Solution (Python):
from math import gcd
k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)

Solution (Python):
from math import gcd
K = int(input())
total = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += gcd(a, gcd(b, c))
print(total)

Solution (Python):
from math import gcd
import itertools

def calc(a,b,c):
    x=gcd(a,b)
    y=gcd(x,c)
    return y

n=int(input())
A=list(itertools.combinations_with_replacement(range(1,n+1), 3))

ans=0
for a,b,c in A:
    if a==b==c:
        ans+=calc(a,b,c)
    elif a!=b and a!=c and b!=c:
        ans+=calc(a,b,c)*6
    else:
        ans+=calc(a,b,c)*3
print(ans)

Solution (Python):
from math import gcd

N = int(input())
answer = 0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            answer += gcd(gcd(a, b), c)
print(answer)

Solution (Python):
from math import gcd
K = int(input())
total = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += gcd(a, gcd(b, c))

print(total)

Solution (Python):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

_sum = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            _sum +=gcd(a, b, c)

print(_sum)

Solution (Python):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())

cnt = 0

for i in range(n):
    i +=1
    for j in range(n):
        j +=1
        for k in range(n):
            k +=1

            cnt += gcd(i,j,k)

print(cnt)

Solution (Python):
import math

n = int(input())
dic = {}

ans = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    tmp1 = math.gcd(i,j)
    for k in range(1,n+1):      
      tmp = math.gcd(tmp1,k)
      
      ans += tmp
      
print(ans)

Solution (Python):
import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        GCD = gcd(i,j)
        if GCD == 1:
            CNT += K
        else:
            for k in range(1, K+1):
                if gcd(GCD,k) != 1:
                    CNT += gcd(GCD,k)
                else:
                    CNT += 1
print(CNT)

Solution (Python):
import math
K=int(input())








s=0

for a in range(K+1):
    s+=a

for a in range(1,K+1):
    for b in range(a+1,K+1):
        s+=math.gcd(a,b)*6

for a in range(1,K+1):
    for b in range(a+1,K+1):
        for c in range(b+1,K+1):
            s+=math.gcd(c,(math.gcd(a,b)))*6

print(s)