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

n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))

nprimes = 0
a = sorted(a)
while True:
    for d in range(2,10001):
        if d==a[0]:
            nprimes+=1
            del a[0]
            break
        elif a[0]%d==0:
            del a[0]
            break
    if len(a) <= 0:
        break

print nprimes

### FIXED CODE ###

def prime(num):
    if num == 0:
        return False
    elif num == 1:
        return False
    elif num == 2:
        return True
    i = 2
    while True:
        if i**2 > num:
            break
        if num%i==0:
            return False
        i += 1
    return True
n = int(raw_input())

nums = []
for _ in range(n):
    a = int(raw_input())
    nums.append(a)

ret = 0
for num in nums:
    if prime(num):
        ret += 1
print ret
### BUGGY CODE ###

def m():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = []
    for a in A: ans.remove(a) if a in ans else ans.append(a)
    return len(ans)

print(m())


### FIXED CODE ###

def m():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    tmp = -1
    cnt = 0
    ans = 0
    for i in range(N):
        if tmp == A[i]:
            cnt +=1
        else:
            if cnt % 2 == 0: pass
            else: ans +=1
            tmp = A[i]
            cnt = 1

    if cnt % 2 == 0: pass
    else: ans += 1
    return ans

print(m())
### BUGGY CODE ###

from collections import defaultdict
import itertools

num = defaultdict(lambda : 0)
n = int(input())
a = [int(i) for i in input().split()]
for i in a:
    num[i] += 1
memo = {i: 0 for i in num.keys()}
total = 0

for i, j in num.items():
    x = len([k for k in itertools.combinations(range(j), 2)])
    memo[i] = x
    total += x
    
for i, j in enumerate(a):
    y = num[j]
    z = memo[j]
    
    if y == 1:
        print(total)
    else:
        print(total - z + len([k for k in itertools.combinations(range(y-1), 2)]))

### FIXED CODE ###

from collections import defaultdict
num = defaultdict(lambda : 0)
n = int(input())
a = [int(i) for i in input().split()]
for i in a:
    num[i] += 1
memo = {i: 0 for i in num.keys()}
total = 0

for i, j in num.items():
    x = int(j * (j - 1) / 2 )
    memo[i] = x
    total += x

for i, j in enumerate(a):
    y = num[j]
    z = memo[j]

    if y == 1:
        print(total)
    else:
        print(total - z + int((y - 1) * (y - 2) / 2))
### BUGGY CODE ###

S = input()
lmax = len(S)
modulo = list([0]*2019)
if(len(S) < 4):
    print(0)
    exit()
for i in range(lmax):
    s = int(S[i:])%2019
    modulo[s] += 1
ans = sum(list(map(lambda x: x*(x-1)//2, modulo)))+modulo[0]
print(ans)

### FIXED CODE ###

S = input()
lmax = len(S)
modulo = list([0]*2019)
mod10 = 10%2019
mod = int(S[-1])%2019
modulo[mod] += 1
for s in reversed(S[:-1]):
    mod = (mod + mod10*int(s))%2019
    modulo[mod] += 1
    mod10 = (mod10*10)%2019
ans = sum(list(map(lambda x: x*(x-1)//2, modulo)))+modulo[0]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    N, M = list(map(int, input().split()))

    L = []
    R = []
    id = list(range(N+1))
    id_set = set(id)
    for _ in range(M):
        if len(id) == 0:
            break
        l, r = list(map(int, input().split()))
        id_set = id_set & set(id[l:r+1])
    print(len(id_set))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    N, M = list(map(int, input().split()))

    L = []
    R = []
    id = list(range(N+1))
    for _ in range(M):
        l, r = list(map(int, input().split()))
        L.append(l)
        R.append(r)

    max_l = max(L)
    min_r = min(R)
    if min_r < max_l:
        print("0")
    else:
        print(min_r - max_l + 1)

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

# ライブラリのインポート
import numpy as np


# メイン関数
def main():
    # 入力データ
    s = input()
    t = input()

    # dpテーブルの作成
    dp = np.zeros((len(s) + 1, len(t) + 1), dtype='int')
    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][j+1], dp[i+1][j])

    # 部分列の復元
    ans = ''
    i = len(s)
    j = len(t)
    while i != 0 and j != 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i] + ans

    # 解答の出力
    print(ans)
    return


# 実行
if __name__ == '__main__':
    main()


### FIXED CODE ###

# メイン関数
def main():
    # 入力データ
    s = input()
    t = input()

    # dpテーブルの作成
    dp = [[0] * (len(t)+1) for i 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][j+1], dp[i+1][j])

    # 部分列の復元
    ans = ''
    i = len(s)
    j = len(t)
    while i != 0 and j != 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i] + ans

    # 解答の出力
    print(ans)
    return


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

N = int(input())
a = list(map(int,input().split()))
b = set(a)

count=0
for i in b:
    if a.count(i)==i:
        pass
    elif a.count(i)>i:
        for j in range(a.count(i)-i):
        	a.remove(i)
        	count+=1
    else:
        for j in range(a.count(i)):
        	a.remove(i)
        	count+=1
print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
s = list(map(int,input().split()))
c = Counter(s)
ans = 0
for i,j in c.items():
    ans += j if j<i else j-i
print(ans)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
lr_list = list()
for _ in range(m):
    lr_list.append(list(map(int, input().split())))

card_list = [i for i in range(1, n + 1)]

max_l = 0
min_r = 1e6

for l, r in lr_list:
    # print(f"{card_list=}")
    # print(f"{max_l=}, {min_r=}")
    if l > max_l or r < min_r:
        max_l = l
        min_r = r
        new_card_list = []
        for card in card_list:
            if card >= max_l and card <= min_r:
                new_card_list.append(card)
        card_list = new_card_list


print(len(card_list))

### FIXED CODE ###

n, m = list(map(int, input().split()))
# lr_list = list()
l_list = list()
r_list = list()
for _ in range(m):
    l, r = list(map(int, input().split()))
    l_list.append(l)
    r_list.append(r)
    # lr_list.append(list(map(int, input().split())))

min_r = min(r_list)
max_l = max(l_list)
if max_l <= min_r:
    print(min_r - max_l + 1)
else:
    print(0)
### BUGGY CODE ###

n,a,b,c,d = map(int,input().split())
s = input()
ng = '##'
if c < d:
    rt1 = s[a-1:c]
    rt2 = s[b-1:d]
    if (ng not in rt1) and (ng not in rt2):
        print('Yes')
    else:
        print('No')
else:
    rt2 = s[b-1:d]
    if ng in rt2:
        print('No')
    else:
        for i in range(b-1, d):
            if s[i] != '#':
                tmp_s = s[:i]+'#'+s[i+1:]
                rt1 = tmp_s[a-1:c]
                if ng not in rt1:
                    print('Yes')
                    exit()
        print('No')

### FIXED CODE ###

n,a,b,c,d = map(int,input().split())
s = input()
ng = '##'
if c < d:
    if (ng in s[b-1:d]) or (ng in s[a-1:c]):
        print('No')
    else:
        print('Yes')
else:
    if ('...' not in s[b-2:d+1]):
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

s=input()
q=int(input())
l=[]
for c in range(q):
    l.append(input())
for c in range(q):
    if l[c]=="1":
        s=s[::-1]
    else:
        j=l[c].split()
        if j[1]=="1":
            s=j[2]+s
        else:
            s=s+j[2]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
l=[]
for c in range(q):
    i=input().split()
    if i==["1"]:
        l.append([1,0,0])
    else:
        l.append([2,int(i[1]),i[2]])
d=0
for c in range(1,q+1):
    if l[-c][0]==1:
        d=d+1
    else:
        l[-c][1]+=d%2
a=""
for c in range(1,q+1):
    if l[-c][0]==2 and l[-c][1]%2==1:
        a=a+l[-c][2]
if d%2==0:
    a=a+s
else:
    a=a+s[::-1]
for c in range(q):
    if l[c][0]==2 and l[c][1]%2==0:
        a=a+l[c][2]
print(a)
### BUGGY CODE ###

import math
from functools import reduce

k = int(input())
sum_gcd = 0

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

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




### FIXED CODE ###

import math

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

gcd_ls = [math.gcd(i, j) for i in rng for j in rng]
ans = [math.gcd(i, l) for i in rng for l in gcd_ls]

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

def main():
    s = input()
    t = list(input())
    N = len(s)

    for tt in t:
        if tt not in s:
            ans = -1
            print(ans)
            exit()

    i = 0
    ans = 0
    r = s * 2
    while t:
        tt = t.pop(0)
        r = r[i::] + s
        cnt = 0
        for rr in r:
            cnt += 1
            if tt == rr:
                break
        ans += cnt
        i = cnt
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect


def search_alphabet_index(string):
    cs = [[] for i in range(26)]
    for i, s in enumerate(string):
        j = ord(s) - ord("a")
        cs[j].append(i)
    return cs


def main():
    S = input()
    T = input()
    N = len(S)

    cs = search_alphabet_index(S)

    for c in set(T):
        if not cs[ord(c) - ord("a")]:
            ans = -1
            print(ans)
            exit()

    rnd = 0
    k = -1
    for t in T:
        ti = ord(t) - ord("a")
        i = bisect(cs[ti], k)
        if i == len(cs[ti]):
            k = cs[ti][0]
            rnd += 1
        else:
            k = cs[ti][i]
    ans = rnd * N + k + 1
    print(ans)


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

N = int(input())
line = [int(i) for i in input().split()]
sum = 1
for num in line:
  sum = sum * num
if sum > 10 ** 18:
  print(-1)
else:
  print(sum)

### FIXED CODE ###

N = int(input())
line = [int(i) for i in input().split()]
sum = 1
line.sort(reverse=True)
if line[len(line) -1]== 0:
  print(0)
  exit()
for num in line:
  sum = sum * num
  if sum > 10 ** 18:
    print(-1)
    exit()
print(sum)
### BUGGY CODE ###

N = int(input())
lst = list(map(int,input().split()))
if N == len(lst) :
    output = 1
    for m in lst :
        output *= m
    if output <= 1000000000000000000 :
        print(output)
    else :
        print(-1)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

n = int(input())
s = input()

count = len(s)

for i in range(0,len(s)):
    s1 = s[:i].count("W")
    s2 = s[i:].count("E")
    count = min(count,s1+s2)
print(count)


### FIXED CODE ###

n = int(input())
s = input()

count = s[1:].count("E")
e = s[1:].count("E")
w = s[1:].count("W")
temp = []
temp.append(count)

for i in range(1,len(s)):
    count = temp[-1]
    if s[i-1] == "W":
        count += 1
    if s[i]=="E":
        count -= 1
    temp.append(count)

print(min(temp))

"""
n = input()
s = input()
l = int(n)
count = 0
for i in range(1,l):
    s1 = set(s[:i])
    s2 = set(s[i:])
    count = max(count,len(s1 & s2))
print(count)




"""
### BUGGY CODE ###

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

listS = list(S)
temp = 0
result = float('inf')
black = 0

for i in range(N):
    temp = listS[:i+1].count('#') + listS[i+1:].count('.')
    if result > temp:
        result = temp

count1 = listS[:N-1].count('#')
print(min(result, count1))


### FIXED CODE ###

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

listS = list(S)

result = listS.count('.')
boundary = listS.count('.')

for i in range(N):
    if listS[i] == '.':
        boundary -= 1
    else:
        boundary += 1
    result = min(result, boundary)

print(result)
### BUGGY CODE ###

import bisect
N = int(input())
Ln = list(map(int,input().split(' ')))

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

def main():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_l = Ln[N-b-1]
            c_threshold = a_l - b_l
            c_list = Ln[0:N-b-1]
            c_idx = bisect.bisect_right(c_list,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx is not None:
                count += len(c_list) - c_idx
    print(count)

def main2():
    '''
    N^2
    '''
    Ln.sort(reverse=True)
    count = 0
    for a in range(N):
        a_l = Ln[a]
        current_min = N-1
        b = a +1
        while b <= current_min:
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                b += 1
                continue
            current_min -= 1
    print(count)
main()

### FIXED CODE ###

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0
for a in range(N):
    a_l = Ln[a]
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
    for b in range(a+1, N):
        if b >= current_min:
            break
        for c in range(b+1,N):
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                break
            current_min -= 1
    '''
print(count)
### BUGGY CODE ###

N=int(input())
*P,=map(int,input().split())

print(sum(list(filter(lambda x: x<P[i], P[:i+1]))==[] for i in range(N)))

### FIXED CODE ###

N=int(input())
*P,=map(int,input().split())

mi=P[0]
cnt=0
for i in range(N):
    if P[i]<mi:mi=P[i]
    if P[i]<=mi:cnt+=1
       
print(cnt)
### BUGGY CODE ###

import sys,gc

class Deque:
    class Cell2:
        def __init__(self, x, y = None, z = None):
            self.data = x
            self.next = y
            self.prev = z

    def __init__(self):
        head = Deque.Cell2(None)
        head.next = head        
        head.prev = head
        self.size = 0
        self.head = head

    def push_front(self, x):
        h = self.head
        q = h.next
        p = Deque.Cell2(x, q, h)
        h.next = p
        q.prev = p
        self.size += 1

    def pop_back(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.prev
        p = q.prev
        p.next = h
        h.prev = p
        self.size -= 1
        return q.data

    def pop_front(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.next
        p = q.next
        p.prev = h
        h.next = p
        self.size -= 1
        return q.data

    def delete(self,x):
        gc.enable()
        h=self.head.next
        while h.data!=x:
            h=h.next
            if h==self.head: return
        q=h.next
        p=h.prev
        q.prev=p
        p.next=q
        self.size -= 1
        gc.disable()
        return

    def __str__(self):
        if self.size == 0: return
        buff = ''
        n = self.size
        cp = self.head.next
        while n > 1:
            buff += '%s ' % cp.data
            cp = cp.next
            n -= 1
        buff += '%s' % cp.data
        return buff
    
gc.disable()
A=Deque()
n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        A.push_front(int(s[1]))
    elif s[0] == 'delete':
        A.delete(int(s[1]))
    elif s[0] == 'deleteFirst':
        A.pop_front()
    elif s[0] == 'deleteLast':
        A.pop_back()
    n -=1
    
print A

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

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

for _ in range(min(K, int(N ** 0.5))):
    lamp = [0 for i in range(N + 1)]
    for i in range(N):
        lamp[max(0, i - A[i])] += 1
        lamp[min(N, i + A[i] + 1)] -= 1

    ans = 0
    for i in range(N):
        ans += lamp[i]
        A[i] = min(ans, N)

[print(A[i], end=' ') if i != N - 1 else print(A[i]) for i in range(N)]


### FIXED CODE ###

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

for i in range(min(K, 50)):
    B = [0 for i in range(N)]
    for j in range(0, N):
        l = max(0, j - A[j])
        r = min(N - 1, j + A[j])
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1

    for j in range(1, N):
        B[j] += B[j - 1]
        
    A = B

[print(i, end=' ') for i in B]
print()
### BUGGY CODE ###

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

mod = 10**9 + 7

import time
start = time.time()


# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return power(x, mod-2)

modinv_table = [-1] * (b+1)
for i in range(1, b+1):
    modinv_table[i] = modinv(i)

end = time.time()
# print("time: ", end - start)

def binomial_coefficients2(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

# (2 ** n - 1) - nCa - nCb
ans = power(2, n) - 1

ans -= (binomial_coefficients2(n, a) + binomial_coefficients2(n, b))
print(ans % mod)


# print(binomial_coefficients2 (5, 2) % mod)


### FIXED CODE ###

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

mod = 10**9 + 7

import time
start = time.time()


# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return pow(x, mod-2, mod)

modinv_table = [-1] * (b+1)
for i in range(1, b+1):
    modinv_table[i] = modinv(i)

end = time.time()
# print("time: ", end - start)

def binomial_coefficients2(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

# (2 ** n - 1) - nCa - nCb
ans = power(2, n) - 1

ans -= (binomial_coefficients2(n, a) + binomial_coefficients2(n, b))
print(ans % mod)


# print(binomial_coefficients2 (5, 2) % mod)
### BUGGY CODE ###

def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200000):
        fact.append(fact[-1]*i % mod)
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    g2 = [set(i) for i in g]
    child = [1]*n  # 子の数
    cnt = 2
    q = [-1, 0]
    while cnt > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            g2[j].remove(i)
            q.append(j)
            cnt += 1
        else:
            q.pop()
            cnt -= 1
            if cnt > 1:
                child[q[-1]] += child[i]
    rank = [(j, i) for i, j in enumerate(child)]
    rank = [j for i, j in sorted(rank)]
    dp = [1]*n
    for i in rank:
        c = child[i]
        ans = fact[c-1]
        temp = 1
        for j in g[i]:
            cj = child[j]
            if cj < c:
                ans = ans*dp[j] % mod
                temp = temp*fact[cj] % mod
        dp[i] = ans*pow(temp, mod-2, mod) % mod
    dp2 = [0]*n
    dp2[0] = dp[0]
    g2 = [set(i) for i in g]
    q = [-1, 0]
    cnt = 2
    while cnt > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            c = child[j]
            temp = fact[n-c]*fact[c-1]
            dp2[j] = dp2[i]*(fact[c]*fact[n-c-1])*pow(temp, mod-2, mod) % mod
            g2[j].remove(i)
            q.append(j)
            cnt += 1
        else:
            q.pop()
            cnt -= 1

    for i in dp2:
        print(i)


main()

### FIXED CODE ###

def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200000):
        fact.append(fact[-1]*i % mod)
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    g2 = [set(i) for i in g]
    child = [1]*n  # 子の数
    q = [-1, 0]
    while len(q) > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
            if len(q) > 1:
                child[q[-1]] += child[i]
    rank = [(j, i) for i, j in enumerate(child)]
    rank = [j for i, j in sorted(rank)]
    dp = [1]*n
    for i in rank:
        c = child[i]
        ans = fact[c-1]
        temp = 1
        for j in g[i]:
            if child[j] < c:
                ans = ans*dp[j] % mod
                temp = temp*fact[child[j]] % mod
        dp[i] = ans*pow(temp, mod-2, mod) % mod
    dp2 = [0]*n
    dp2[0] = dp[0]
    g2 = [set(i) for i in g]
    q = [-1, 0]
    while len(q) > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            c = child[j]
            temp = fact[n-c]*fact[c-1]
            dp2[j] = dp2[i]*(fact[c]*fact[n-c-1])*pow(temp, mod-2, mod) % mod
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
            if len(q) > 1:
                child[q[-1]] += child[i]

    for i in dp2:
        print(i)


main()