Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[float('inf') for _ in range(10**5+10)]for _ in range(n+1)]
#dp[i][j]=i個目までの品物を選んだとき、価値をjにする最小の重さ
dp[0][0]=0
for i in range(n):
    w,v=l[i]
    for j in range(10**5+10):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        if j+v<10**5+10:
            dp[i+1][j+v]=min(dp[i+1][j+v],dp[i][j]+w)
    for j in range(10**5+9):
        dp[i+1][-2-j]=min(dp[i+1][-2-j],dp[i+1][-1-j])
for i in range(10**5+10):
    if dp[-1][i]>mw:
        print(i-1)
        break

### FIXED CODE ###

n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[float('inf') for _ in range(10**5+10)]for _ in range(n+1)]
#dp[i][j]=i個目までの品物を選んだとき、価値をjにする最小の重さ
dp[0][0]=0
for i in range(n):
    w,v=l[i]
    for j in range(10**5+10):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        if j+v<10**5+10:
            dp[i+1][j+v]=min(dp[i+1][j+v],dp[i][j]+w)
    for j in range(10**5+9):
        dp[i+1][-2-j]=min(dp[i+1][-2-j],dp[i+1][-1-j])
for i in range(10**5+10):
    if dp[-1][i]>mw:
        print(i-1)
        break
### BUGGY CODE ###

def main():
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    ans = [None] * Q
    A_Counter = Counter(A)
    for q in range(Q):
        B, C = map(int, input().split())
        A_Counter[C] += A_Counter[B]
        A_Counter[B] = 0

        ans[q] = sum(A_Counter.elements())

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    ans = [None] * Q
    Asum = sum(A)
    A_Counter = Counter(A)
    for q in range(Q):
        B, C = map(int, input().split())
        Asum = Asum + (C-B)*A_Counter[B]
        A_Counter[C] += A_Counter[B]
        A_Counter[B] = 0

        ans[q] = Asum

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from math import *
a,b,c,d = map(int,input().split())
f =(c*d)//gcd(c,d)
r = f
rock = 2
compteur= 0
if f<=b:
  while f<=b:
    if f>=a and f<=b:
      compteur +=1
    f = r*rock
    rock += 1
div1 = ((b//c)-(a//c))
div2 = ((b//d)-(a//d))
if  a%c == 0:
  div1+=1
if a%d ==0:
  div2 +=1
roger =(div1+div2)-compteur
mm = (b-a)+1
print(mm-roger)

### FIXED CODE ###

from math import *
a,b,c,d = map(int,input().split())
f =(c*d)//gcd(c,d)
r = f
rock = 2
compteur= (b//f)-(a//f)
if a%f==0:
  compteur +=1
div1 = ((b//c)-(a//c))
div2 = ((b//d)-(a//d))
if  a%c == 0:
  div1+=1
if a%d ==0:
  div2 +=1
roger =(div1+div2)-compteur
mm = (b-a)+1
print(mm-roger)
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
num_pos = {}

for y, line in enumerate(A):
    for x, num in enumerate(line):
        num_pos[num] = (x, y)

for l, r in LR:
    cost = 0
    for d in range(0, r-l, D):
        cost += abs(num_pos[l+d][0] - num_pos[l+d+D][0]) + abs(num_pos[l+d][1] - num_pos[l+d+D][1])
    print(cost)

### FIXED CODE ###

import sys
Input = sys.stdin.readline

H, W, D = map(int, Input().split())
A = [list(map(int, Input().split())) for _ in range(H)]
Q = int(Input())
LR = [list(map(int, Input().split())) for _ in range(Q)]
num_pos = {}

for y, line in enumerate(A):
    for x, num in enumerate(line):
        num_pos[num] = (x, y)

cost_table = {}
for num in range(1, H*W+1):
    if num <= D:
        cost_table[num] = 0
    else:
        i, j = num_pos[num-D]
        x, y = num_pos[num]
        cost_table[num] = abs(i - x) + abs(j - y) + cost_table[num-D]

for l, r in LR:
    print(cost_table[r] - cost_table[l])
### BUGGY CODE ###

import heapq
n,k=map(int,input().split())
can=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        can.append(j)
table=[0]*n
table[0]=1
que=[0]
heapq.heapify(que)
can.sort()
while que:
    now=heapq.heappop(que)
    for j in can:
        if now+j<n:
            table[now+j]+=table[now]
            if not now+j in que:
                heapq.heappush(que,now+j)
print(table[-1]%998244353)

### FIXED CODE ###

p=998244353
n,k=map(int,input().split())
kukan=[]
for i in range(k):
    l,r=map(int,input().split())
    kukan.append((l,r))
dp=[0]*n
sdp=[0]*(n+1)
dp[0]=1
sdp[1]=1
for i in range(1,n):
    for l,r in kukan:
        left=max(0,i-r)
        right=max(0,i-l+1)
        dp[i]=(dp[i]+sdp[right]-sdp[left])%p
    sdp[i+1]=(sdp[i]+dp[i])%p
print(dp[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
prices = [int(p) for p in input().split()]
for _ in range(m):
    j, p = max(enumerate(prices), key=lambda x: x[1])
    prices[j] //= 2
print(sum(prices))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
prices = [-int(p) for p in input().split()]
heapq.heapify(prices)
for _ in range(m):
  p = heapq.heappop(prices)
  heapq.heappush(prices, p / 2)
print(-sum(int(p) for p in prices))
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))
B=set(A)
# print(A)
# print(B)

# シミュレーションする方法で解いてみる
C=set()
for i in range(N):
  if A[i] in C:
    C.remove(A[i])
  else:
    C=C|{A[i]}
  # print(C)
print(len(C))

### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))
A.sort()
# print(A)

# 想定解で解くしかない
res=0
i=0
while i<N:
  c=A[i]
  f=0
  while i<N and A[i]==c:
    f+=1
    i+=1
  res+=f%2
print(res)
### BUGGY CODE ###

N = int(input())
S = input()
s = set()
max_count = len(set(S)) ** 3
for x in range(N - 2):
    for y in range(x + 1, N  - 1):
        for z in set(S[y + 1:]):
            s.add(f"{S[x]}{S[y]}{z}")
            if len(s) == max_count:
                print(max_count)
                exit()
print(len(s))

### FIXED CODE ###

N = int(input())
S = input()

ret = 0
for x in range(10):
    for y in range(10):
        for z in range(10):
            a = S.find(str(x))
            if a != -1:
                b = S.find(str(y), a + 1)
                if b != -1:
                    c = S.find(str(z), b + 1)
                    if c != -1:
                        ret += 1
print(ret)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
count=0
for i in range(n//2):
    k=sum(a[i:n-i])
    if k%m==0:
        count+=1
    s=a[i]
    if s%m==0:
        count+=1
    if (k-s)%m==0:
        count+=1
    for j in range(i+1,n-i-1):
        s+=a[j]
        if s%m==0:
            count+=1
        if (k-s)%m==0:
            count+=1
if n%2==1:
    if a[n//2]%m==0:
        count+=1
print(count)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
count=0
sum=0
alist=[0]
for i in a:
    sum+=i
    alist.append(sum%m)
alist.sort()
k=-1
n=0
for j in alist:
    if k!=j:
        count+=(n*(n-1)/2)
        n=0
    n+=1
    k=j
count+=(n*(n-1)/2)
print(int(count))
### BUGGY CODE ###

t=int(input())
for _ in range(t):
    a,b,c,d=map(int,input().split())
    e=b*(max((a-c)//b,1))
    a-=e
    while a>c:
        a-=b
    if a<0:
        print('No')
        continue
    if d<b:
        print('No')
        continue
    if c<=b and d>b:
        """
        while a<=c:
            a+=(d-b)
        """
        a+=(d-b)*(c//(d-b))
        while a<=c:
            a+=(d-b)
        while a-(d-b)>c:
            a-=(d-b)
        if a<b:
            print('No')
            continue
    print('Yes')

### FIXED CODE ###

from fractions import*
_,*t=open(0)
for t in t:
  a,b,c,d=map(int,t.split())
  g=gcd(b,d)
  print('YNeos'[b>min(a,d)or b-g+a%g>c::2])
### BUGGY CODE ###

import numpy as np
N=int(input())
A=list(map(int,(input().split())))
npArray = np.array(A)
npArray=npArray.copy()
Q=int(input())
B=[]
C=[]
ans=0
for _ in range(Q):
  L, R = map(int,(input().split()))
  B.append(L)
  C.append(R)

for i in range(Q):
  upNpArray = np.where(npArray == B[i], C[i], npArray)
  print(np.sum(upNpArray))
  npArray=upNpArray.copy()

### FIXED CODE ###

import collections
import copy
N=int(input())
A=list(map(int,(input().split())))
ans=sum(A)
Q=int(input())
col = collections.Counter(A)

for i in range(Q):
  L, R = map(int,(input().split()))
  sa=(R-L)*col[L]
  col[R]+=copy.copy(col[L])
  col[L]=0
  ans= ans+sa
  print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split(' '))
    p_list = list(map(int, input().split(' ')))
    max_p_sum = 0
    sum_list = list()
    for n in range(0, N - K + 1, 1):
        if max_p_sum < sum(p_list[n: n + K]):
            max_p_sum = sum(p_list[n: n + K])
            sum_list = p_list[n: n + K]
    expected_value = [(1 + s) / 2 for s in sum_list]
    print(sum(expected_value))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def expected_value(x):
    x = int(x)
    return (x + 1) / 2


def main():
    N, K = map(int, input().split(' '))
    p_list = list(map(expected_value, input().split(' ')))
    cumulative_list = [0]
    for p in p_list:
        cumulative_list.append(cumulative_list[-1] + p)
    max_len = 0
    for i in range(0, N - K + 1):
        if max_len < cumulative_list[i + K] - cumulative_list[i]: max_len = cumulative_list[i + K] - cumulative_list[i]
    print(max_len)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))


K = int(input())
def main():
    k = 7
    count = 1
    re = 1
    if K %2==0:
        print(-1)
        return
    while True:
        if k % K == 0:
            print(count)
            return
        re =  (re*10)%K
        k = (k+7*re)%K
        count += 1


main()


### FIXED CODE ###

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))


K = int(input())
def main():
    k = 7
    count = 1
    re = 1
    if K % 2==0:
        print(-1)
        return
    while True:
        if k % K == 0:
            print(count)
            return
        re =  (re*10)%K
        k = (k+7*re)%K
        count += 1
        if count >= 10**7:
            print(-1)
            return


main()
### BUGGY CODE ###

def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
    for n in range(N + 1):
        dp[n][0] = 1
    for n in range(1, N + 1):
        dp_left = dp[n][0]  # dp[n][k - 1]
        for k in range(1, K + 1):
            val = dp_left + dp[n - 1][k]
            kk = k - A[n - 1] - 1
            if kk >= 0:
                val -= dp[n - 1][kk]
            val %= MOD
            dp[n][k] = val
            dp_left = val
    print(dp[N][K])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
    for n in range(N + 1):
        dp[n][0] = 1
    for n in range(1, N + 1):
        dp_left = dp[n][0]  # dp[n][k - 1]
        for k in range(1, K + 1):
            val = dp_left + dp[n - 1][k]
            kk = k - A[n - 1] - 1
            if kk >= 0:
                val -= dp[n - 1][kk]
            val %= MOD
            dp[n][k] = val
            dp_left = val
    print(dp[N][K])


if __name__ == '__main__':
    main()
### BUGGY CODE ###


def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * max(N,K)
    dp[0] = 0

    for i in range(N):
        j = 0
        L = min(K, i)
        while j <= L:
            #print(i)
            if dp[i] > dp[i-j] + abs(h[i]-h[i-j]):
                dp[i] = dp[i-j] + abs(h[i]-h[i-j])
            j += 1
    print(dp[N-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * N
    dp[0] = 0

    for i in range(N):
        dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(min(K,i)+1)])
    print(dp[N-1])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

index = defaultdict(list)

for i, s in enumerate(S):
    if s == "R":
        index["R"].append(i)
    elif s == "G":
        index["G"].append(i)
    else:
        index["B"].append(i)

G = sorted(index["G"])
R = sorted(index["R"])
B = sorted(index["B"])

count = 0
for r in R:
    for g in G:
        for b in B:
            l = sorted([r, g, b])
            if l[1]-l[0] != l[2]-l[1]:
                count += 1

            # s = min(r, g, b)
            # l = max(r, g, b)
            # if r != s and r != l:
            #     m = r
            # if g != s and g != l:
            #     m = g
            # if b != s and b != l:
            #     m = b
            # if m - s != l - m:
            #     count += 1
            

print(count)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    else:
        B.append(i)

# print(R, G, B)

ans = len(R) * len(G) * len(B)

count = 0

for i in range(N):
    for j in range(N):
        if i < j:
            k = j + (j - i)
            if k < N:
                if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                    count += 1
print(ans - count)
### BUGGY CODE ###

h,n = map(int,input().split())
data = []
ans = 0
M = -1
for _ in range(n):
    a,b = map(int,input().split())
    data.append((a,b))
    M = max(a,M)
dp = [float("inf") for _ in range(h+M)]
dp[0] = 0
for i,j in data:
    for k in range(h+M-1):
        if k+i <= h+M-1:
            dp[k+i] = min(dp[k]+j,dp[k+i])
print(min(dp[h:]))

### FIXED CODE ###

h,n = map(int,input().split())
data = []
ans = 0
M = -1
for _ in range(n):
    a,b = map(int,input().split())
    data.append((a,b))
    M = max(a,M)
dp = [float("inf") for _ in range(h+M)]
dp[0] = 0
for i,j in data:
    for k in range(h+M-1):
        if k+i <= h+M-1:
            dp[k+i] = min(dp[k]+j,dp[k+i])
print(min(dp[h:]))
### BUGGY CODE ###

S = input()
Q = int(input())
# queries = []
# for _ in range(Q):
#   q = list(input().split()) # 文字列のリスト
#   queries.append(q)

r_count = 0
# for query in queries:
for query in range(Q):
  query = list(input().split())
  t = query[0]
  if (t == '1'):
    r_count += 1
  elif (t == '2'):
    f = query[1]
    new_S = ""
    if(f == '1' and (r_count % 2 == 0)):
      new_S = query[2] + S
    elif(f == '1' and (r_count % 2 == 1)):
      new_S = S + query[2]
    elif(f == '2' and (r_count % 2 == 0)):
      new_S = S + query[2]
    elif(f == '2' and (r_count % 2 == 1)):
      new_S = query[2] + S
    S = new_S

if (r_count % 2 == 1):
  for i, s in enumerate(reversed(S)):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
else:
  print(S)


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

r_count = 0
for query in range(Q):
  query = deque(list(input().split()))
  t = query[0]
  if (t == '1'):
    r_count += 1
  elif (t == '2'):
    f = query[1]
    if(f == '1' and (r_count % 2 == 0)):
      S.appendleft(query[2])
    elif(f == '1' and (r_count % 2 == 1)):
      S.append(query[2])
    elif(f == '2' and (r_count % 2 == 0)):
      S.append(query[2])
    elif(f == '2' and (r_count % 2 == 1)):
      S.appendleft(query[2])

if (r_count % 2 == 1):
  for i, s in enumerate(reversed(S)):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
else:
  for i, s in enumerate(S):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
### BUGGY CODE ###

from collections import deque
N = int(input())

d = deque([0])
table = [-1]*(N+1)
table[0] = 0
while d:
    i = d.popleft()
    j = 6
    k = 9
    if (i < N):
        if table[i+1] == -1:
            table[i+1] = table[i] + 1
        d.append(i+1)

    while i + j <= N:
        if table[i+j] == -1:
            table[i+j] = table[i] + 1
            d.append(j)
        j *= 6
    while i + k <= N:
        if table[i+k] == -1:
            table[i+k] = table[i] + 1
            d.append(k)
        k *= 9
    if table[N] != -1:
        break
print(table[N])            

### FIXED CODE ###

N = int(input())
dp = [0] * (N+1)
for i in range(1,N+1):
    dp[i] = float('inf')
    power = 1
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] +1)
        power *= 6
    power = 9
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 9
print(dp[N])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ones,twos,threes=0,0,0
for i in l:
    if i==1:
        ones+=1
    elif i==2:
        twos+=1
    else:
        threes+=1
max_ones=ones+twos+threes
max_twos=twos+threes
max_threes=threes
dp=[[[0.0]*(n+1)for i in range(n+1)]for j in range(n+1)]
for k in range(max_threes+1):
    for j in range(max_twos+1-k):
        for i in range(max_ones+1-j-k):
            if i+j+k==0:
                continue
            else:
                dp[i][j][k]=n/(i+j+k)
                if i>0:
                    dp[i][j][k]+=(dp[i-1][j][k]*i)/(i+j+k)
                if j>0:
                    dp[i][j][k]+=(dp[i+1][j-1][k]*j)/(i+j+k)
                if k>0:
                    dp[i][j][k]+=(dp[i][j+1][k-1]*k)/(i+j+k)
print(dp[i][j][k])




            

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
ones,twos,threes=0,0,0
for i in l:
    if i==1:
        ones+=1
    elif i==2:
        twos+=1
    else:
        threes+=1
max_ones=ones+twos+threes
max_twos=twos+threes
max_threes=threes
dp=[[[0.0]*(n+1)for i in range(n+1)]for j in range(n+1)]
for k in range(max_threes+1):
    for j in range(max_twos+1-k):
        for i in range(max_ones+1-j-k):
            if (i+j+k)==0:
                continue
            else:
                dp[i][j][k]=n/(i+j+k)
                if i>0:
                    dp[i][j][k]+=(dp[i-1][j][k]*i)/(i+j+k)
                if j>0:
                    dp[i][j][k]+=(dp[i+1][j-1][k]*j)/(i+j+k)
                if k>0:
                    dp[i][j][k]+=(dp[i][j+1][k-1]*k)/(i+j+k)
print(dp[i][j][k])
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()

def test(n):
    cnt = 0
    for i in range(1,100):
        for j in range(1,100):
            for k in range(1,100):
                if (i+j+k)**2 == n + (i*j + j*k + k*i):
                    cnt += 1 
                if (i+j+k)**2 - (i*j + j*k + k*i) > n:
                    break
    return cnt

for i in range(N):
    print(test(i+1))


### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()

ans = [0 for _ in range(10050)]

for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
           v = (i+j+k)**2 - (i*j + j*k + k*i)
           if v < 10050:
            ans[v] += 1

for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

import numpy as np
s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        c = np.array(pre)
        for j in range(1,10):
            te = t*j % 13
            c += pre[13-te:] + pre[:13-te]
        c %= n
        pre = c.tolist()
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5]%n)

### FIXED CODE ###

s = input()
pre = [1]+[0]*12
n = 10**9 + 7
tem = [[i*j%13 for i in range(10)] for j in range(13)]
t = 1
for i in range(len(s)):
    if s[-1*i-1] > "9":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = [pre[i-te] for i in range(13)]
    t = t*10 % 13
print(pre[5])
### BUGGY CODE ###

import sys
def solve(n,m,a):
    ans = ""
    bb = {i+1:[] for i in range(n)}
    for [s1,s2] in a:
        bb[s1].append(s2)
    b = [i for i in bb.values()]
    for i in range(len(b)):
        b[i].sort()
    for i in range(m):
        ans += str(a[i][0]).zfill(6) + str(b[a[i][0]-1].index(a[i][1])+1).zfill(6) + "\n"
    
    return ans 
def readQuestion():
    ws = sys.stdin.readline().strip().split()
    N = int(ws[0])
    M = int(ws[1])
    ls_PY = [list(map(int, sys.stdin.readline().strip().split())) for j in range(M)]
    return (N, M, ls_PY)

def main():
    N, M, ls_PY = readQuestion()
    answer = solve(N, M, ls_PY)
    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N,M=map(int,input().split())
PY=[list(map(int,input().split()))+[i] for i in range(M)] #定義終了
 
PY.sort(key= lambda x:x[1])
num=[0]*N
w=[""]*M
 
for p,y,i in PY:
	num[p-1]+=1
	w[i]=str(p).zfill(6)+str(num[p-1]).zfill(6)

for i in range(M):
  	print(w[i])
### BUGGY CODE ###

import math

k = int(input())
ans = 0

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


### FIXED CODE ###

import math

k = int(input())
ans = 0

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