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

# coding:utf-8
int_max = 2 ** 63 - 1

def get_cost(start, end):
    return 1 if start == '.' and end == '.' else 2 ** 63 - 1


def warshall_floyd(n, ad_table):
    """
    ワーシャルフロイド法
    :param n: 頂点の数
    :param ad_table: 隣接行列
    """
    for k in range(n):            # 経由する頂点
        for i in range(n):        # 始点
            for j in range(n):    # 終点
                ad_table[i][j] = min(ad_table[i][j], ad_table[i][k] + ad_table[k][j])

    return ad_table


def main():

    H, W = map(int, input().split(' '))
    ad_table = [[int_max for _ in range(H*W)] for _ in range(H*W)]
    maze = []
    for _ in range(H):
        maze.append(input())

    for si in range(H):
        for sj in range(W):
            for ti in range(H):
                for tj in range(W):
                    if si == ti and sj == tj:
                        ad_table[(si*W)+sj][(ti*W)+tj] = 0
                    elif (abs(si - ti) == 1 and sj - tj == 0) or (si - ti == 0 and abs(sj - tj) == 1):
                        ad_table[(si*W)+sj][(ti*W)+tj] = get_cost(maze[si][sj], maze[ti][tj])

    res = warshall_floyd(H*W, ad_table)
    ans = -1
    for l in res:
        for n in l:
            if n != int_max and ans < n:
                ans = n
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding:utf-8
from scipy.sparse.csgraph import floyd_warshall

int_max = 2 ** 63 - 1

def get_cost(start, end):
    return 1 if start == '.' and end == '.' else 2 ** 63 - 1


def main():

    H, W = map(int, input().split(' '))
    ad_table = [[int_max for _ in range(H*W)] for _ in range(H*W)]
    maze = []
    for _ in range(H):
        maze.append(input())

    for si in range(H):
        for sj in range(W):
            for ti in range(H):
                for tj in range(W):
                    if si == ti and sj == tj:
                        ad_table[(si*W)+sj][(ti*W)+tj] = 0
                    elif (abs(si - ti) == 1 and sj - tj == 0) or (si - ti == 0 and abs(sj - tj) == 1):
                        ad_table[(si*W)+sj][(ti*W)+tj] = get_cost(maze[si][sj], maze[ti][tj])

    res = floyd_warshall(ad_table)
    ans = -1
    for i in range(H*W):
        for j in range(i+1,H*W):
            if res[i][j] != int_max:
                ans = max(res[i][j], ans)
    print(int(ans))

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

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

A.sort(reverse=True)

cnt=1

for i in range(1,N):
    a=A.pop()
    b=A.pop()
    if 2*a>=b:
        cnt+=1
    else:
        cnt=1
    A.append(a+b)
    A.sort(reverse=True)

print(cnt)

### FIXED CODE ###

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

su=sum(A)
cnt=1
for i in range(N-1,0,-1):
    if (su-A[i])*2<A[i]:
        break
    else:
        cnt+=1
        su=su-A[i]

print(cnt)
### BUGGY CODE ###

s = input()
t = input()

dp = [["" for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            dp[i+1][j+1] = dp[i+1][j] if len(dp[i+1][j]) >= len(dp[i][j+1]) else dp[i][j+1]

print(dp[-1][-1])

### FIXED CODE ###

s = input()
t = input()

dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
n = dp[-1][-1]
i = len(s)
j = len(t)
while n > 0:
    if dp[i][j] == dp[i-1][j]:
        i -=1
    elif dp[i][j] == dp[i][j-1]:
        j -=1
    elif dp[i][j] == dp[i-1][j-1] + 1:
        ans = s[i-1] + ans
        n -= 1
        i -= 1
        j -= 1

print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()

index = 0
pt = XH[0][0] + 2 * D
ht = (-(-XH[0][1] // A)) * A
answer = -(-XH[0][1] // A)

while 1:
  for i in range(index, N):
    if XH[i][0] <= pt:
      XH[i][1] -= ht
    else:
      break
  flag = 1
  for i in range(index, N):
    if XH[i][1] > 0:
      pt = XH[i][0] + 2 * D
      ht = (-(-XH[i][1] // A)) * A
      answer += -(-XH[i][1] // A)
      index = i
      flag = 0
      break
  if flag == 1:
    break
                 
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

from bisect import bisect_right

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)


index = 0
pt = XH[index][0] + 2 * D
ht = (-(-XH[index][1] // A)) * A
minus = ht
answer = -(-XH[index][1] // A)
bi = bisect_right(X, pt)
check[bi] += ht

while 1:
  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  minus += ht
  answer += -(-XH[index][1] // A)
  bi = bisect_right(X, pt)
  check[bi] += ht
                 
print(answer)
### BUGGY CODE ###

n = int(input())
s = input()
S = list(s[i] for i in range(len(s)))
x = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if {S[i], S[j], S[k]}=={"R", "G", "B"} and i+k != 2*j:
        x += 1
print(x)
        

### FIXED CODE ###

n = int(input())
s = input()
a = s.count("R")
b = s.count("G")
c = s.count("B")
z = a*b*c
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)
x = 0
for i in R:
  for j in G:
    if 0 <= 2*j-i <= n-1 and s[2*j-i]=="B":
      x+=1
    if 0 <= 2*i-j <= n-1 and s[2*i-j]=="B":
      x+=1
    if (i+j)%2==0 and s[(i+j)//2]=="B":
      x+=1
print(z-x)
### BUGGY CODE ###

mod=10**9+7
def pairORSum(arr, n) : 
    ans = 0     # Initialize result 
  
    # Consider all pairs (arr[i], arr[j)  
    # such that i < j 
    for i in range(0, n) : 
          
        for j in range(i + 1, n) : 
              
            ans = ans + (arr[i] ^ arr[j]) 
              
    return ans 
      
  
# Driver Code 
n=int(input())
arr=list(map(int,input().split()))
print(pairORSum(arr, n)%mod) 

### FIXED CODE ###

N=int(input())
bin_a="".join(["{:060b}".format(a) for a in map(int, input().split())])
mod=10**9+7
xor=0
for d in range(60):
  ones=bin_a[59-d::60].count('1')
  xor+=2**d*ones*(N-ones)    
print(xor%mod)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]

b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7
  
if not 1 in a:
  b[1]=1
  
for j in range(2,n+1):
  if not j in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n])    
    
  
  
  



### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
a=[0]*(n+1)
dp=[0]*(n+1)
dp[0]=1
for i in range(m):
    a[int(input())]=1
    
if a[1]==1:
    dp[1]=0
else:
    dp[1]=1
    
for j in range(2,n+1):
    if a[j]==0:
        dp[j]=dp[j-1]+dp[j-2] 
                  
print(dp[n]%mod)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(2, N+1):
    t = 0
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t
K = N
ans = ""
while K > 0:
    for a in A:
        xa = x[a]
        if K >= xa and dp[K] == dp[K-xa] + 1:
            if dp[K] == 1 and K != xa:
                continue
            ans += str(a)
            K -= xa
            break
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
INF = float('inf')
for i in range(1, N+1):
    t = -INF
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t

K = N
k = dp[N]
ans = ""
while k > 0:
    for a in A:
        xa = x[a]
        if K >= xa and k == dp[K-xa] + 1:
            ans += str(a)
            K -= xa
            k -= 1
            break
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [-1]
for i in range(1, m+1):
    a = a + [0]
    a[i] = int(input())
a =a+[n+1] 
for i in range(m+1):
    a[i]=a[i+1] - a[i]-1
b=[0]
b=b+[1]
for i in range(2, max(a)+1):
    b=b+[0]
    b[i] = (b[i-1] + b[i-2])%(10**9+7)
s=1
for i in range(m+1):
    s=(s*b[a[i]])%(10**9+7)
print(s)

### FIXED CODE ###

n,m = map(int,input().split())
c=10**9+7
a = [-1 for _ in range(m + 1)]
for i in range(1, m+1):
    a[i] = int(input())
a =a+[n+1] 
for i in range(m+1):
    a[i]=a[i+1] - a[i]-1
b=[0 for _ in range(max(a) + 1)]
b[1]=1
for i in range(2, max(a)+1):
    b[i] = (b[i-1] + b[i-2])%c
s=1
for i in range(m+1):
    s=(s*b[a[i]])%c
print(s)
### BUGGY CODE ###

n = int(input())
a = [input() for i in range(n)]
if a.count(max(a)) >= 2:
    for i in range(n):
        print(max(a))
else:
    b = a.copy()
    b.remove(max(b))
    c = max(b)
    for i in range(n):
        if a[i] == max(a):
            print(c)
        else:
            print(max(a))




### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a, reverse=True)
for i in range(n):
    if b[0] == b[1]:
        print(b[0])
    else:
        if a[i] == b[0]:
            print(b[1])
        else:
            print(b[0])
### BUGGY CODE ###

n = int(input())    

s = [1]*(n+1)
ans = 1
for i in range(2,n+1):
    for j in range(i,n+1,i):
        s[j] += 1
    ans += (i * s[i])

print(ans)


### FIXED CODE ###

from numba import njit
import numpy as np


@njit("i8(i8)")
def solve(n):
    ans = 1
    res = np.ones(n + 1, dtype=np.int64)
    for i in range(2, n + 1):
        for j in range(i, n + 1, i):
            res[j] += 1
        ans += i * res[i]
    return ans


N = int(input())
print(solve(N))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


N, M_a, M_b = [int(x) for x in input().split()]
inf = 100000
t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
t[0][0] = 0
for _ in range(N):
    ai, bi, ci = [int(x) for x in input().split()]
    for ta in reversed(range(ai, len(t))):
        for tb in reversed(range(bi, len(t[0]))):
            t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
ans = min(
    t[k * M_a][k * M_b]
    for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
)
print(-1 if ans >= inf else ans)


### FIXED CODE ###

#!/usr/bin/env python3
def solve():
    N, M_a, M_b = [int(x) for x in input().split()]
    inf = 100000
    t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
    t[0][0] = 0
    for _ in range(N):
        ai, bi, ci = [int(x) for x in input().split()]
        for ta in reversed(range(ai, len(t))):
            for tb in reversed(range(bi, len(t[0]))):
                t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
    ans = min(
        t[k * M_a][k * M_b]
        for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
    )
    print(-1 if ans >= inf else ans)


solve()
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
b = 1
for i in a:
  b = b * i
if b > 10 ** 18:
  print('-1')
else:
  print(b)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
ans = 1
for i in a:
    ans *= i
    if ans > 10**18:
        print("-1")
        break
else:
    print(ans)
### BUGGY CODE ###

N=int(input())
number=list(map(int,input().split()))
MOD = 10**9+7
sum=0
total=0
for i in range(N-1):
    for j in range(i+1,N):
        sum=(sum+(((number[i]%MOD)*(number[j]%MOD))%MOD))%MOD
print(sum)

### FIXED CODE ###

N=int(input())
number=list(map(int,input().split()))
MOD = 10**9+7
sum=sum(number)
s=sum%MOD
ans=0
for i in number:
    s-=i
    s%=MOD
    ans+=s*i
    ans%=MOD
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
gcd_list = []
min_element = min(A)
max_element = max(A)

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

for i in range(n):
    y = A[i]
    for j in range(min_element, max_element + 1):
        A[i] = j
        x = A[0]
        for k in range(1, n):
            x = gcd(x, A[k])
        gcd_list.append(x)
    A[i] = y
print(max(gcd_list))


### FIXED CODE ###

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

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    if a % b == 0:
        return b
    return gcd(b, a%b)

L = [0]; R = [0]
for i in range(N-1):
    L.append(gcd(L[i], A[i]))
    R.append(gcd(R[i], A[N-1-i]))

maxGCD = 1
for j in range(N):
    maxGCD = max(maxGCD, gcd(L[j], R[N-j-1]))
print(maxGCD)
### BUGGY CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
br = set(ar)
count = 0
for r in br:
    count += ar.count(r) - 1
if count % 2 == 0:
    print(a - count)
else:
    print(a - count - 1)

### FIXED CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
br = set(ar)
count = len(ar) - len(br)
if count % 2 == 0:
    print(a - count)
else:
    print(a - count - 1)
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=[]
for i in range(N):
    row=[]
    for j in range(N):
        if i == j:
            row.append(0)
        elif abs(i - j) == 1 or i == X and j == Y or i == Y and j == X:
            row.append(1)
        else:
            row.append(2000)
    gyoretu.append(row)
G=csgraph_from_dense(gyoretu)
#print(G)
d=floyd_warshall(G)
#print(d)
#for k in range(N):
#    for i in range(N):
#        for j in range(N):
#            if gyoretu[i][j]> gyoretu[i][k] + gyoretu[k][j]:
#                gyoretu[i][j] =gyoretu[i][k] + gyoretu[k][j]
array=[]
for i in range(N):
        #array += gyoretu[i][i:]
        array += list(d[i][i:])
c=Counter(array)
for i in range(1, N):
    print(c[i])

### FIXED CODE ###

[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
count=[0 for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        count[min(abs(i-j),abs(i-X)+1+abs(Y-j),abs(i-Y)+1+abs(X-j))]+=1
#print(array)


for i in range(1,N):
        print(count[i])

#print(count)
### BUGGY CODE ###

from collections import deque

s = deque(input())

q = int(input())

for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        s.reverse()
    else:
        if A[1] == '1':
            s.appendleft(A[2])
        else:
            s.append(A[2])
print("".join(list(s)))

### FIXED CODE ###

from collections import deque

s = deque(input())

q = int(input())
r = 0
for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        r = (r + 1)%2
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] == '2' and r % 2 == 1):
            s.appendleft(A[2])
        else:
            s.append(A[2])

if r == 1:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

N=int(input())
import numpy as np
A=np.zeros(N)
B=np.zeros(N)
for i in range(0,N):
  A[i],B[i] = map(int,input().split())

BB=list(set(list(B)))
for b in BB:
  if np.sum(A[B<=b])>b:
    print('No')
    break
else:
  print('Yes')

### FIXED CODE ###

import sys
import bisect
import numpy as np
input = sys.stdin.readline
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
    A[i],B[i]=[int(x) for x in input().split()]
matrix = np.vstack((np.array(A),np.array(B)))
matrix = matrix[:, np.argsort(matrix[1])]
time=0
capacity=0
for a,b in zip(matrix[0],matrix[1]):
    capacity += (b-time) - a
    time = b
    if capacity <0:
        print('No')
        sys.exit()
    #print(capacity,a,b)
print('Yes')
### BUGGY CODE ###

n = int(input())
L = list(map(int,input().split()))

if len(L)==1:
      flag = "Yes"
for i in range(1,n):
      if max(L[:i]) - min(L[i:]) >=2:
            flag = "No"
      else:
            flag = "Yes"

print(flag)


### FIXED CODE ###

N = int(input())
lis_h = list(map(int, input().split()))

for i in range(N,1,-1):
    if lis_h[i - 1] < lis_h[i - 2]:
        lis_h[i - 2] -= 1
        if lis_h[i - 1] < lis_h[i - 2]:
            print("No")
            exit()
print("Yes")
### BUGGY CODE ###

import itertools
from heapq import heapify, heappop, heappush, heappushpop

class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap


heap = []  # ヒープといっても順序を工夫したただのリスト

q = PriorityQueue(heap) #ここでインスタンスを作ってます
n = int(input())
l = tuple(map(int, input().split()))
total = 0
mod = 1000000007
L = itertools.combinations(l, 2)
for a,b in L:
    num = ((a % mod) * (b % mod)) % mod
    q.push(num)
print(sum(heap) % mod)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
mod = 1000000007
q = sum(l)
ans = 0
for i in range(len(l)):
    q -= l[i]
    ans += l[i] * q % mod
print(ans % mod)
### BUGGY CODE ###

from numpy import array
n = int(input()) / 2
d = array([int(i) for i in input().split()])

c = 0
b = 0
for i in sorted(d):
    if sum(d < i) == n:
        c += i - b
    b = i
print(c)


### FIXED CODE ###

N = int(input())
ds = sorted([int(i) for i in input().split()])

print(ds[N//2] - ds[N//2 - 1])
### BUGGY CODE ###

R, C, K = map(int, input().split())
dp = [[[0] * 4 for _ in range(C + 1)]for _ in range(R + 1)]
grid = [[0] * C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    grid[r - 1][c - 1] = v
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            # chmax(dp[i][j][k + 1], dp[i][j][k] + grid[i][j])
            dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k] + grid[i][j])
        for k in range(4):
            dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k])
            dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
ans = 0
for k in range(4):
    ans = max(ans, dp[R - 1][C - 1][k])
print(ans)


### FIXED CODE ###

R, C, K = map(int, input().split())
# dp = [[[0] * 4 for _ in range(C + 1)]for _ in range(R + 1)]
dp2 = [[[0] * (C + 1) for _ in range(R + 1)]for _ in range(4)]

grid = [[0] * C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    grid[r - 1][c - 1] = v
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            # chmax(dp[i][j][k + 1], dp[i][j][k] + grid[i][j])
            # dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k] + grid[i][j])
            dp2[k + 1][i][j] = max(dp2[k + 1][i][j], dp2[k][i][j] + grid[i][j])
        for k in range(4):
            # dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k])
            dp2[0][i + 1][j] = max(dp2[0][i + 1][j], dp2[k][i][j])
            # dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
            dp2[k][i][j + 1] = max(dp2[k][i][j + 1], dp2[k][i][j])
ans = 0
for k in range(4):
    # ans = max(ans, dp[R - 1][C - 1][k])
    ans = max(ans, dp2[k][R - 1][C - 1])
print(ans)

# print(dp[R - 1][C - 1][3])
### BUGGY CODE ###

n,m=map(int, input().split())
l=[]
for _ in range (0,m):
    l.append(input())
wa_total=0
ac_total=0
ac_list=[]

for value in l:
    if str(value.split()[1]) == "AC":
        if not str(value.split()[0]) in ac_list:
            ac_list.append(str(value.split()[0]))
            for i in range(0,l.index(value)):
                if l[i].split()[0] == value.split()[0]:
                    if l[i].split()[1] == "WA":
                        wa_total+=1
            l.remove(value)

print (len(ac_list), wa_total)

### FIXED CODE ###

n,m = map(int,input().split())
ac = 0
wa = 0
wa_d = {}
ac_d = {}
for i in range(1,n+1):
    ac_d[str(i)] = False
    wa_d[str(i)] = 0

for _ in range(m):
    p,s = input().split()
    if s == "AC":
        if ac_d[p]:
            pass
        else:
            wa += wa_d[p]
            ac += 1
            ac_d[p] = True 
    else:
        wa_d[p] += 1

print (ac,wa)
### BUGGY CODE ###

n = int(input())

L = [0] * (n + 1)
for x in range(1, n + 1):
    for y in range(1, n - x):
        for z in range(1, n - x - y):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for l in L[1:]:
    print(l)


### FIXED CODE ###

import math

n = int(input())
max = int(math.sqrt(n) + 1)
L = [0] * (n + 1)
for x in range(1, max):
    for y in range(1, max):
        for z in range(1, max):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for i in range(1, n + 1):
    print(L[i])
### BUGGY CODE ###

q = int(input())

l = []
x = ""
y = ""
"""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex == 0 and yIndex == 0:
        return 0
    elif xIndex == 0:
        return l[yIndex - 1][0]
    elif yIndex == 0:
        return l[0][xIndex - 1]
    elif x[xIndex] == y[yIndex]:
        return 1 + l[yIndex - 1][xIndex - 1]
    else:
        if l[yIndex][xIndex - 1] > l[yIndex - 1][xIndex]:
            return l[yIndex][xIndex - 1]
        else:
            return l[yIndex - 1][xIndex]
        #return max(l[yIndex][xIndex - 1], l[yIndex - 1][xIndex])
 """
for i in range(q):
    x = input()
    y = input()
 
    yLen = len(y)
    xLen = len(x)
    l = [[0] * xLen for j in range(yLen)]

    for j in range(yLen):
        for k in range(xLen):
            if k == 0 and j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = 0
            elif k == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j - 1][k]
            elif j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j][k - 1]
            elif x[k] == y[j]:
                l[j][k] = 1 + l[j - 1][k - 1]
            else:
                if l[j][k - 1] > l[j - 1][k]:
                    l[j][k] = l[j][k - 1]
                else:
                    l[j][k] = l[j - 1][k]
            #l[j][k] = lcs(j, k)
 
    print(l[yLen- 1][xLen - 1])



### FIXED CODE ###

q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

    print(len(l[-1]) - 1)