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

import sys
from math import sqrt
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        upper = 50
        #print("n={}, upper={}".format(n, upper))
        for x in range(1, upper):
            for y in range(1, upper):
                for z in range(1, upper):
                    if (x + y + z)**2 - (x*y + y*z + z*x) == n:
                        ans += 1
        print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import sqrt
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        #print("n={}".format(n))
        for x in range(1, 41):
            # x==yの時
            if n - 2*x*x >= 0:
                z0 = round(sqrt(n - 2*x*x) - x)
                for z in range(z0 - 2, z0 + 3):
                    if (x + z)**2 + 2*x*x == n:
                        if x == z:
                            #print(x, x, x)
                            ans += 1
                        elif x < z:
                            #print(x, x, z)
                            ans += 3
            # x < y <= zの時
            if n - x**2 >= 0:
                upper = round(sqrt((n - x**2) / 3) - x / 3) + 5
                for y in range(x+1, upper):
                    val = x**2 + x*y + y**2
                    if (x + y)**2 - 4 * (val - n) >= 0:
                        z0 = round((-(x+y) + sqrt((x + y)**2 - 4 * (val - n))) / 2)
                        for z in range(z0-2, z0+3):
                            if z**2 + (x + y)*z + val == n:
                                if y == z:
                                    #print(x, y, z)
                                    ans += 3
                                elif y < z:
                                    #print(x, y, z)
                                    ans += 6
        print(ans)




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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    ans = [0] * 63
    for i in range(63):
        x0 = len([j for j in range(N) if not (A[j]>>i)&1])
        x1 = len([j for j in range(N) if (A[j]>>i)&1])
        ans[i] = x0*x1

    x = 0
    for i in range(len(ans)):
        # print(i, 2**i)
        x += (2 ** i) * ans[i] % MOD

    print(x%MOD)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    ans = [0] * 60
    
    
    for i in range(60):
        # x0 = len([j for j in range(N) if not (A[j]>>i)&1])
        # x1 = len([j for j in range(N) if (A[j]>>i)&1])
        x0 = 0
        x1 = 0
        for j in range(N):
            if (A[j]>>i)&1:
                x1 += 1
            else:
                x0 += 1

        ans[i] = x0*x1

    x = 0
    for i in range(len(ans)):
        # print(i, 2**i)
        x += pow(2, i) * ans[i] % MOD

    print(x%MOD)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

n = int(input())
a_list = list(map(int, input().split()))
a_list2 = a_list

ans = [0] * n
c = a_list2.count(1)
a_list2 = [i for i in a_list2 if i != 1]
ans[0] = c

for i in range(n-1):
    a_buka = a_list[i] + 1
    count = a_list2.count(a_buka)
    a_list2 = [j for j in a_list2 if j != a_buka]
    ans[i+1] = count

for x in ans:
    print(x)


### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans = [0] * n

for a in a_list:
    ans[a-1] += 1

for i in ans:
    print(i)
### BUGGY CODE ###

import sys
from math import factorial
n = int(input())
c_ls = [int(i) for i in sys.stdin.readline().split()]
c_ls.sort(reverse=True)
MOD = 10**9+7

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

res = 0
for i in range(n-1, -1, -1):
    hoge = sum([nCr(i, j) * j * 2 ** (n - i - 1) for j in range(1,i+1)])
    res += (2 ** (n - 1) + hoge) * c_ls[i]
    res %= MOD
res = res * (2**n) % MOD
print(res)

### FIXED CODE ###

import sys

n = int(input())
c_ls = [int(i) for i in sys.stdin.readline().split()]
c_ls.sort(reverse=True)
MOD = 10 ** 9 + 7

res = 0
for i, c in enumerate(c_ls):
    res += (i + 2) * c % MOD
    res %= MOD
res = res * (4 ** (n - 1)) % MOD
print(int(res))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc134/tasks/abc134_e

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = []

for _ in range(N):
    A.append(INT())

DP = [0] * N
DP[0] = 1
inc_dic = {0: 0}
color = 0
for i in range(1, N):
    if A[i-1] < A[i]:
        DP[i] = DP[i-1]
        inc_dic[color] = i
        continue
    else:
        for j in inc_dic.keys():
            if A[inc_dic[j]] < A[i]:
                DP[i] = DP[i-1]
                inc_dic[j] = i
                color = j
                break
        else:
            DP[i] = DP[i-1] + 1
            color = max(inc_dic.keys()) + 1
            inc_dic[color] = i

print(DP[-1])



### FIXED CODE ###

# https://atcoder.jp/contests/abc134/tasks/abc134_e

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
from collections import deque
from bisect import bisect_left

N = INT()
A = []

for _ in range(N):
    A.append(INT())

t = deque([A[0]])
for a in A[1:]:
    i = bisect_left(t, a) - 1
    if i == -1:
        t.appendleft(a)
    else:
        t[i] = a

print(len(t))
### BUGGY CODE ###

from math import factorial

def nCr(n,r):
  c = min(r,n-r)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi *= (n+1-i)%(10**9+7)
    bunbo *= i%(10**9+7)
  return bunshi*pow(bunbo,10**9+5,10**9+7)%(10**9+7)
  

#入力
n,a,b = map(int,input().split())

#答え用の関数
ans = 0
#Σ(k 1~n) nCk = 2^n
ans += pow(2,n,10**9+7)
ans -= (nCr(n,a)+nCr(n,b)+1)
ans = ans%(10**9+7)
print(ans)

### FIXED CODE ###

n,a,b = map(int,input().split())
m = 10**9+7

def nCr(n_, r_, m_):
  c = min(r_ , n_ - r_)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi = bunshi * (n_+1-i) % m_
    bunbo = bunbo * i % m_
  return bunshi * pow(bunbo, m_-2, m_) % m_


ans = pow(2,n,m)-1
ans -= nCr(n,a,m)
ans %= m
ans -= nCr(n,b,m)
ans %= m
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
PY = [list(map(int,input().split())) for _ in range(M)]
PY_originals = tuple(PY)
N_counter = [0] * N
M_counter = [0] * M

PY.sort(key=lambda val: val[1])
i = 0

for P,Y in PY:
    N_counter[P-1] += 1
    M_counter[i] = N_counter[P-1]
    i += 1

for i in PY_originals:
    ans = str(i[0]).zfill(6)+str(M_counter[PY.index(i)]).zfill(6)
    print(ans)


### FIXED CODE ###

N,M = map(int, input().split())

PY = [[i] for i in range(1,M+1)]

for i in range(M):
    temp1, temp2 = map(int, input().split())
    PY[i].append(temp1)
    PY[i].append(temp2)


PY.sort(key=lambda val: val[2])
# print(PY)
PY.sort(key=lambda val: val[1])
# print(PY)
city = 0

for i, value in enumerate(PY):
    if value[1] != city:
        j = 0
    j += 1
    value.append(j)
    city = value[1]

PY.sort(key=lambda val:val[0])

# print(PY)

for i in PY:
    ans = str(i[1]).zfill(6)+str(i[3]).zfill(6)
    print(ans)
### BUGGY CODE ###

import math
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [math.inf]*(h+10000)
dp[0] = 0
for a, b in ab:
    for i in range(h+10000):
        dp[i] = min(dp[i], dp[i-a]+b)
print(min(dp[h:]))

# print(dp[:h+100])


### FIXED CODE ###

import math
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [math.inf]*(h+10000)
dp[0] = 0
for a, b in ab:
    for i in range(h+10000):
        dp[i] = min(dp[i], dp[i-a]+b)
print(min(dp[h:]))

# print(dp[:h+100])
### BUGGY CODE ###

import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))

day=0

match=[0 for i in range(n)]

while True:
  day+=1
  check=[True for i in range(n)]
  for i in range(n):
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
      
    if i==n-1:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
        
print(day)

### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

n = int(input())

c, s, f = [], [], []
for _ in range(n-1):
    x,y,z = map(int,input().split())
    c.append(x)
    s.append(y)
    f.append(z)

anss =[]
for i in range(n-1):
    tmp = 0
    for j in range(i, n-1):
        k = 0
        while 1:
            if tmp <= s[j] + f[j] * k:
                tmp = s[j] + f[j] * k + c[j]
                break
            else:
                k += 1
    else:
        anss.append(tmp)
else:
    anss += [0]

for ans in anss:
    print(ans)

### FIXED CODE ###

n = int(input())

c, s, f = [], [], []
for _ in range(n-1):
    x,y,z = map(int,input().split())
    c.append(x)
    s.append(y)
    f.append(z)

anss =[]
for i in range(n-1):
    tmp = 0
    for j in range(i, n-1):
        k = 0
        while 1:
            if tmp <= s[j] + f[j] * k:
                tmp = s[j] + f[j] * k + c[j]
                break
            else:
                k += 1
    else:
        anss.append(tmp)
else:
    anss += [0]

for ans in anss:
    print(ans)
### BUGGY CODE ###

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

ans = 0
for i in A:
    if ans != 0:
        ans = ans * i
    else:
        ans = i

if ans > 10 ** 18:
    print("-1")
else:
    print(ans)


### FIXED CODE ###

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

A.sort()
ans = 0

if A[0] == 0:
    print(ans)
    exit()

for i in A:
    if ans != 0:
        ans = ans * i
    else:
        ans = i
    if ans > 1000000000000000000:
        print("-1")
        exit()

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

from itertools import accumulate

N, X = map(int, input().split())
BLUs = [tuple(map(int, input().split())) for _ in range(N)]

vs = [(L*B + U*(X-B), i) for i, (B, L, U) in enumerate(BLUs)]
vs.sort(reverse=True)

accVs = list(accumulate([0] + vs, lambda accX, X: accX + X[0]))
D0 = -sum([L*B for B, L, U in BLUs])

def isOK(k):
    q = k // X
    r = k % X
    for odr, (v, i) in enumerate(vs):
        B, L, U = BLUs[i]
        d = D0
        if odr < q:
            d += accVs[q+1] - v
        else:
            d += accVs[q]
        if r <= B:
            d += L*r
        else:
            d += L*B + U*(r-B)
        if d >= 0:
            return True
    return False

ng, ok = -1, N*X
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline

def solve():
    N, X = map(int, input().split())
    tests = []
    D0 = 0
    for _ in range(N):
        B, L, U = map(int, input().split())
        v = L*B + U*(X-B)
        tests.append((v, B, L, U))
        D0 -= L*B
    tests.sort(reverse=True)

    accV = 0
    accVs = [0]
    for v, B, L, U in tests:
        accV += v
        accVs.append(accV)

    def isOK(k):
        q = k // X
        r = k % X
        accV = accVs[q+1]
        for v, B, L, U in tests[:q]:
            d = D0 + accV - v
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        accV = accVs[q]
        for v, B, L, U in tests[q:]:
            d = D0 + accV
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        return False

    ng, ok = -1, N*X
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    return ok


print(solve())
### BUGGY CODE ###

import numpy as np
n = int(input())
a = []
for i in range(n):
  s = list(input())
  a .append(s)
a = np.array(a)
ans = 0
for i in range(n):
  c = np.roll(a,i,axis=0)
  for j in range(n):
    d = np.roll(c,j,axis=1)
    if np.array_equal(d,d.T):
      ans += 1
print(ans)

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
n = int(input())
a = np.array([list(input().rstrip()) for i in range(n)])
ans = 0
for i in range(n):
  c = np.roll(a,i,axis=0)
  if np.array_equal(c,c.T):
    ans += 1
print(ans*n)
### BUGGY CODE ###

H,W,D = [int(n) for n in raw_input().split(" ")]
A = [[None] * (W + 1)] * (H + 1)
Location = {}
for h in range(1,H + 1):
	A[h][1:W+1] = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A[h]):
		Location[a] = (h, w)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for l in L:
	C[l,l] = 0
for q in range(1,Q+1):
	l = L[q]
	r = R[q]
	cur_dist = 0
	for x1 in range(l, r, D):
		x2 = x1 + D
		if (x1, r) in C:
			C[(l,r)] = C[l, x1] + C[(x1,r)]
			break
		if (x1,x2) not in C:
			h1, w1 = Location[x1]
			h2, w2 = Location[x2]
			C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + C[(x1,x2)]
		C[(l,x2)] = cur_dist
	print C[(l,r)]

### FIXED CODE ###

H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for d in range(1,D+1):
	C[d,d] = 0
	cur_dist = 0
	for x1 in range(d, H * W + 1, D):
		x2 = x1 + D
		if x2 > H * W: 
			break
		h1, w1 = Location[x1]
		h2, w2 = Location[x2]
		#C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + abs(h1 - h2) + abs(w1 - w2)
		C[(d,x2)] = cur_dist
	
for q in range(1,Q+1):
	l, r = L[q], R[q]
	d = l % D
	if d == 0: 
		d = D
	print (C[(d,r)] - C[(d,l)])
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
ls = [1] * (N+10)
for i in range(K):
    ls[K-1] *= A[i]
for i in range(K, N):
    ls[i] = ls[i-1]//A[i-K] * A[i]
    if ls[i] > ls[i-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N, K = inpl()
A = inpl()
for i in range(K, N):
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')

# -----------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)
### BUGGY CODE ###

from collections import deque

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

L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

par = [-1]*N

cnt = [0]*N

q = deque([0])
while len(q) :
    u = q.popleft()
    for v in L[u] :
        if v == par[u] :
            continue
        par[v] = u
        q.append(v)

for i in range(Q) :
    p,x = map(int,input().split())
    p -= 1
    q = deque([p])
    while len(q) :
        u = q.popleft()
        cnt[u] += x
        for v in L[u] :
            if v != par[u] :
                q.append(v)

print(*cnt)


### FIXED CODE ###

from collections import deque

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

L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

par = [-1]*N

cnt = [0]*N

for i in range(Q) :
    p,x = map(int,input().split())
    p -= 1
    cnt[p] += x

q = deque([0])
while len(q) :
    u = q.popleft()
    for v in L[u] :
        if v == par[u] :
            continue
        par[v] = u
        cnt[v] += cnt[u]
        q.append(v)


"""
for i in range(Q) :
    p,x = map(int,input().split())
    p -= 1
    q = deque([p])
    while len(q) :
        u = q.popleft()
        cnt[u] += x
        for v in L[u] :
            if v != par[u] :
                q.append(v)
"""
print(*cnt)
### BUGGY CODE ###

N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

max_count = 0
for i in range(2,M):
  count = 0
  for j in range(i,M,i):
    count += counts[j]
  max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

### FIXED CODE ###

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

def get_count(p):
  integers = [1 for _ in range(p+1)]
  integers[0] = 0
  integers[1] = 0
  counts = [0 for _ in range(p+1)]
  for a in A:
    counts[a] += 1
  answer = 0
  for i in range(p+1):
    if integers[i] >= 1:
      count = 0
      for j in range(i,p+1,i):
        count += counts[j]
        integers[j] = 0
      answer = max(answer,count)
  return answer

count = get_count(max(A))
if count == N:
  answer = 'not coprime'
elif count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q):
    q = input()
    if q == "1":
        S = S[::-1]
    else:
        if q[2] == "1":
            S = q[-1] + S
        if q[2] == "2":
            S = S + q[-1]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

left = ""
right = ""
cnt = 0

for i in range(Q):
    q = input()
    if q == "1":
        cnt += 1
    elif (cnt%2 == 0 and q[2] == "1") or (cnt%2 == 1 and q[2] == "2"):
        left += q[4]
    else:
        right += q[4]

if cnt%2 == 0:
    ans = left[::-1] + S + right
else:
    ans = right[::-1] + S[::-1] + left

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

n=int(input())
a=[i for i in input().split()]
b=[]

for c,j in enumerate(a):
    if c%2 == 0:
        b.append(j)
    else:
        b.insert(0,j)

if len(a)%2==0:
    print(' '.join(b))
else:
    print(' '.join(b[::-1]))


### FIXED CODE ###

n=int(input())
a=[i for i in input().split()]
b=[]
if len(a)%2==0:
    print(' '.join(a[-1::-2]) + ' ' + ' '.join(a[::2]))
else:
    print(' '.join(a[-1::-2]) + ' ' + ' '.join(a[1::2]))
### BUGGY CODE ###

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

l = []
for i in range(n):
    x = a.index(i + 1) + 1
    l.append(x)

l = list(map(str, l))
print(' '.join(l))

### FIXED CODE ###

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

l = [0] * n

for i in range(n):
    l[a[i] - 1] = i + 1

print(*l)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def nop(h,w):
    if l[h-1][w-1]=='#':
        return 0
    if h==1:
        return left(w)
    elif w==1:
        return up(h)
    return nop(h-1,w)+nop(h,w-1)
def up(h):
    if l[h-1][0]=='#':
        return 0
    if h==1:
        return 1
    return up(h-1)
def left(w):
    if l[0][w-1]=='#':
        return 0
    if w==1:
        return 1
    return left(w-1)
h,w=map(int,input().split())
l=[list(input()) for _ in range(h)]
print(nop(h,w)%(10**9+7))


### FIXED CODE ###

h,w=map(int,input().split())
l=[[1 if i=='.' else 0 for i in input()] for _ in range(h)]
for i in range(w):
    if l[0][i]==0:
        for j in range(i+1,w):
            l[0][j]=0
        break
for i in range(h):
    if l[i][0]==0:
        for j in range(i+1,h):
            l[j][0]=0
        break
for i in range(1,h):
    for j in range(1,w):
        if l[i][j]!=0:
            l[i][j]=l[i-1][j]+l[i][j-1]
print(l[h-1][w-1]%(10**9+7))
### BUGGY CODE ###

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    A.sort()
    nums = list()
    for a in A:
        is_target = True
        for n in nums:
            if a % n == 0:
                is_target = False
                break
        if is_target:
            nums.append(a)
    print(len(list(filter(lambda n: counter[n] == 1, nums))))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    searched = [0 for _ in range(10 ** 6 + 1)]
    ans = 0
    for i in range(1, 10 ** 6 + 1):
        if counter[i] == 0:
            continue
        if searched[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1, ((10 ** 6) // i) + 1):
            searched[i * j] = 1
    print(ans)


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

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
output = np.zeros(N)

output[N//2:]=A[N//2:]

t = N//2-1
for j in range(N//2):
    for i in range(N//(t+1)-1):
        output[t]= (output[t]+output[(t+1)*(i+2)-1])%2
    output[t]=int(output[t] != A[t])
    t -= 1

ans = ""
flag = 0
for j in range(N):
    if output[j]==1:
        ans += str(j+1) + " "
        flag += 1
print(flag)
if flag > 0:
    ans = ans[:-1]
    print(ans)

### FIXED CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

B = [0]*N
for i in range(N):
    X = N-i
    P = B[X-1]
    Q = A[X-1]
    if P==Q:
        B[X-1] = 0
    else:
        XDL = make_divisors(X)
        for XD in XDL:
            if XD==X:
                B[XD-1] = 1
            else:
                B[XD-1] = 1 - B[XD-1]
out = []
cnt = 0
for i in range(N):
    if B[i]==1:
        out.append(i+1)
        cnt+=1
print(cnt)
if len(out)>0:
    print(*out)
### BUGGY CODE ###

n,m=map(int, input().split())
ko=[[] for i in range(n)]
oya=[[] for i in range(n)]
rank=[0]*n 

for i in range(n-1+m):
    a,b=map(int, input().split())
    ko[b-1].append(a-1)
    oya[a-1].append(b-1)
s=0
for i in range(n):
    if len(ko[i])==0:s=i
p=[s]
nr=1
ans=[0]*n
while p:
    now=p.pop(0)
    nr=rank[now]+1
    p+=oya[now]
    for i in oya[now]:
        rank[i]=nr
        ans[i]=now+1
for i in ans:print(i)

### FIXED CODE ###

n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
for s in range(n):
    if not oya[s]:break
q=[[s,ko[s]]]
ans=[0]*n
while q:
    now,nex=q.pop()
    for i in nex:
        oya[i].remove(now)
        if not oya[i]:
            ans[i]=now+1
            q.append([i,ko[i]])
for i in ans:print(i)