Harryxun/stf_run huggingface dataset:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
###############################################################################\
def power(a,p,m):
    res=1
    while(p>0):
        if p&1:
            res=(res*a)%m
        a=(a*a)%m
        p//=2
    return res%m
n=int(input())
s=input()
A=list(int(i) for i in s)
R=[]
for i in range(n-1,-1,-1):
    R.append(A[i])
one=0
for e in A:
    if e==1:
        one+=1
max=one+1
min=one-1
ansmax=0
ansmin=0
#print(one)
for i in range(n):
    ansmax=(ansmax+power(2,i,max)*(R[i]))%max
    ansmin=(ansmin+power(2,i,min)*R[i])%min
def popcount(z):
    ans=0
    while(z!=0):
        if z%2==1:
            ans+=1
        z//=2
    return ans
#print(ansmax,ansmin)
B=[]
for i in range(n):
    if R[i]==1:
        r=(ansmin-power(2,i,min))%min
        count=1
        while(r!=0):
            count+=1
            r=r%popcount(r)
        B.append(count)
        #print(count)
    else:
        r=(ansmax+power(2,i,max))%max
        count=1
        while(r!=0):
            count+=1
            r=r%popcount(r)
        B.append(count)
B.reverse()
for ele in B:
    print(ele)


### FIXED CODE ###

from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
###############################################################################\
def power(a,p,m):
    if m==0:
        return 0
    res=1
    while(p>0):
        if p&1:
            res=(res*a)%m
        a=(a*a)%m
        p//=2
    return res%m
n=int(input())
s=input()
A=list(int(i) for i in s)
R=[]
for i in range(n-1,-1,-1):
    R.append(A[i])
one=0
for e in A:
    if e==1:
        one+=1
max=one+1
min=one-1
ansmax=0
ansmin=0
#print(one)
for i in range(n):
    ansmax=(ansmax+power(2,i,max)*(R[i]))%max
    if min!=0:
        ansmin=(ansmin+power(2,i,min)*R[i])%min
def popcount(z):
    ans=0
    while(z!=0):
        if z%2==1:
            ans+=1
        z//=2
    return ans
#print(ansmax,ansmin)
B=[]
for i in range(n):
    if R[i]==1:
        if min!=0:
            r=(ansmin-power(2,i,min))%min
            count=1
            while(r!=0):
                count+=1
                r=r%popcount(r)
        else:
            count=0
        B.append(count)
    else:
        r=(ansmax+power(2,i,max))%max
        count=1
        while(r!=0):
            count+=1
            r=r%popcount(r)
        B.append(count)
B.reverse()
for ele in B:
    print(ele)
import itertools
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

def tentou(X):
  ret=0
  BIT=[0]*128
  BIT.insert(0,0)
  for i1 in range(n):
    x=X[i1]+1
    ret+=i1-bitsum(BIT,x)
    bitadd(BIT,x,1)
  return ret
N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2+1):
  for com in itertools.combinations(N,2*_):
    E,O=[],[]
    for j in range(n):
      if j not in com:
        if j%2==0:
          E.append(A[j]*100+j)
        else:
          O.append(A[j]*100+j)
      else:
        if j%2==0:
          O.append(B[j]*100+j)
        else:
          E.append(B[j]*100+j)
    if len(E)!=(n+1)//2:
      continue
    else:
      E.sort()
      O.sort()

      chk=True
      C=[E[0]%100]
      prev=E[0]//100
      for i in range(1,n):
        ii=i//2
        if i%2==0:
          C.append(E[ii]%100)
          if E[ii]//100<prev:
            chk=False
            break
          else:
            prev=E[ii]//100
        else:
          C.append(O[ii]%100)
          if O[ii]//100<prev:
            chk=False
            break
          else:
            prev=O[ii]//100
    
    if chk:
      ans=min(ans,tentou(C))
print(-1 if ans==float("inf") else ans)



### FIXED CODE ###

import itertools
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=64:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

def tentou(X):
  ret=0
  BIT=[0]*64
  BIT.insert(0,0)
  for i1 in range(n):
    x=X[i1]+1
    ret+=i1-bitsum(BIT,x)
    bitadd(BIT,x,1)
  return ret
N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2+1):
  for com in itertools.combinations(N,2*_):
    i=0
    for ura in com:
      i+=2**ura
    E,O=[],[]
    for j in range(n):
      if i&(1<<j)==0:
        if j%2==0:
          E.append(A[j]*100+j)
        else:
          O.append(A[j]*100+j)
      else:
        if j%2==0:
          O.append(B[j]*100+j)
        else:
          E.append(B[j]*100+j)
    if len(E)!=(n+1)//2:
      continue
    else:
      E.sort()
      O.sort()

      chk=True
      C=[E[0]%100]
      prev=E[0]//100
      for i in range(1,n):
        ii=i//2
        if i%2==0:
          C.append(E[ii]%100)
          if E[ii]//100<prev:
            chk=False
            break
          else:
            prev=E[ii]//100
        else:
          C.append(O[ii]%100)
          if O[ii]//100<prev:
            chk=False
            break
          else:
            prev=O[ii]//100
    
    if chk:
      ans=min(ans,tentou(C))
print(-1 if ans==float("inf") else ans)
n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
G=[]

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

def dfs(now):
    global group
    for next in friend[now]:
        if visited[next]==False:
            visited[next]=True
            group.append(next)
            dfs(next)
            
    return group
group=[]
visited=[False]*n
for i in range(n):
        visited=[False]*(n)
        visited[i]=True
        G.append(dfs(i))
        group=[]
for i in range(n):
    ans=set(G[i])-set(friend[i])-set(block[i])
    print(len(ans))



### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ
 
    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]
 
    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
 
    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)
 
    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]
 

n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
group=[[]for i in range(n)]
uf=UnionFind(n)

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    uf.unite(a-1,b-1)

for i in range(k):
    c,d=map(int,input().split())
    if uf.is_same(c-1,d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)

for i in range(n):
    ans=uf.group_size(i)-1-len(friend[i])-len(block[i])
    print(ans)
a,b,c=map(int,input().split())
print(print 'A' if max(abs(b-a),abs(c-a))==abs(b-a) else 'B')

### FIXED CODE ###

a,b,c=map(int,input().split())
print('A' if min(abs(b-a),abs(c-a))==abs(b-a) else 'B')
N = int(input())
a = []
for i in range(N):
    a.append(map(int, input())

for i in range(N):
    v = a[i]
    j = i-1
    while j>=0 and a[j]>v:
        a[j+1] = a[j]
        j = j-1
        a[j+1] = v
    print(a) 


### FIXED CODE ###

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


for i in range(N):
    v = b[i]
    j = i-1
    while j>=0 and b[j]>v:
        b[j+1] = b[j]
        j = j-1
        b[j+1] = v
    print(" ".join([str(n) for n in b]))
from collections import Counter

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

# a =< x < a + 1:
min_a = int(a/0.08)

max_a = int((a+1)/0.08)

min_b = int(b/0.10)

max_b = int((b+1)/0.10)

ans_list = []

while(min_a < max_a):
    ans_list.append(min_a)
    min_a += 1
while(min_b < max_b):
    ans_list.append(min_b)
    min_b += 1
ans_list.sort()
ans = Counter(ans_list)
for i in ans:
    if ans[i] > 1:
        print(i)
        flag = False
        break
if flag:
    print(-1)

### FIXED CODE ###

import math

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

ans =  -1

for i in range(2000):
    if math.floor(i * 0.08) == a and math.floor(i * 0.10) == b:
        ans = i
        break

print(ans)
N = int(input())
An = list(map(int, input().split()))
sum = 1
for i in range(N):
  sum *= An[i]
  if sum > 1e18:
    print(-1)
    quit()
  else sum == 0:
    print(0)
    quit()
print(sum)

### FIXED CODE ###

N = int(input())
An = list(map(int, input().split()))
sum = 1
max = 10 ** 18
if 0 in An:
  print(0)
  quit()
for i in range(N):
  sum *= An[i]
  if sum > max:
    print(-1)
    quit()
print(sum)
10 5
4 7 10 6 5

### FIXED CODE ###

X, N = list(map(int,input().split()))
if N !=0:
  P = list(map(int,input().split()))
  ab = 100
  for i in range(-100,200):
    if i not in P:
      if abs(X-i)<ab:
        ab = abs(X-i)
        ans = i
  print(ans)
else:
  print(X)
N,M = map(int, input().split())
a = [int(input()) for i in range(M)]

def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b

if M == 0:
    print(fib(N))

flag = 0
if M >= 2:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            flag += 1

if flag >= 1:
    print(0)


else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

    print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

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

def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b if n >= 0 else 0

if M == 0:
    ans = fib(N) % (10**9+7)


elif M == 1:
    ans = fib(a[0]-1) * fib(N-a[0]-1)
    ans %= (10**9+7)

else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)
n, x = [int(i) i in input().split()]

3 <= n <= 100

if n == x == 0:
    break

for a in range(n):
    for b in range(a):
        for c in range(b):
             a + b + c == x
             return

### FIXED CODE ###

while True:
    n, x = [int(i) for i in input().split()]

    if n == x == 0:
        break

    count = 0
    for s in range(1, n+1):
        for m in range(s+1, n):
            for e in range(m+1, n+1):
                if x == sum([s, m, e]):
                    count += 1

    print(count)
D, G = map(int, input().split())

P = []
C = []
C2 = []
for i in range(D):
    p, c = map(int, input().split())
    P.append(p)
    c += p * (i+1) * 100
    C.append(c)
    C2.append(c/(p+1))

sort_C2 = sorted(C2, reverse=1)

num = 0
point = 0
question = [i for i in range(D-1, -1, -1)]


for i in sort_C2:
    x = C2.index(i)
    if C[x] <= G - point:
        num += P[x]
        point += C[x]
        question.remove(x)
    else:
        y = question[0]
        n = -(-(G - point)) // ((y+1) * 100)
        if P[y] < n:
            num += P[y]
        else:
            num += n
        break

print(num)



### FIXED CODE ###

import math
D, G = map(int, input().split())

P = []
C = []
for i in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)

answer = sum(P)
for i in range(2**D):
    point = 0
    x = -1
    now_answer = 0
    for j in range(D):
        if i >> j & 1:
            point += P[j] * (j+1) * 100 + C[j]
            now_answer += P[j]
        else:
            x = j

    if G <= point:
        answer = min(now_answer, answer)
    else:
        n = math.ceil((G - point) / ((x+1) * 100))
        if n < P[x]:
            now_answer += n
            answer = min(now_answer, answer)

print(answer)
def binarySeach(t):
	left,right = 0,n
	while right > left:
		mid = (left+right) // 2
		if S[mid] == t:
			return True
		elif S[mid] > t:
			mid = right
		else:
			mid = left
	return False

n = int(input())
S = [int(s) for s in input().split()]
q = int(input())
T = [int(s) for s in input().split()]

print(sum([binarySerch(t) for t in T]))

### FIXED CODE ###

def binarySearch(t):
	left,right = 0,n
	while right > left+1:
		mid = (left+right) // 2
		if S[mid] == t:
			return True
		elif S[mid] > t:
			right = mid
		else:
			left = mid
	return False

n = int(input())
S = [int(s) for s in input().split()]
q = int(input())
T = [int(s) for s in input().split()]

print(sum([binarySearch(t) for t in T]))
import numpy as np
N, K, Q = input().split()
A = np.array([int(input()) for i in range(int(Q))])
T = np.full(int(N), int(K))
unique, counts = np.unique(A, return_counts=True)
s =  dict(zip(unique, counts))
for key, value in s.items():
    T[0:(key-1)] -= value
    T[key:len(T)] -= value
for i in T:
    if i <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

from collections import Counter
import numpy as np

N, K, Q = input().split()
A = np.array([int(input()) for i in range(int(Q))])
T = np.full(int(N), int(K))
T -= int(Q)
#unique, counts = np.unique(A, return_counts=True)
#s =  dict(zip(unique, counts))
s = Counter(A)
for key, value in s.items():
    T[(key-1)] += value
for i in T:
    if i <= 0:
        print("No")
    else:
        print("Yes")
import sys
import numpy as np
N=int(input())
nums=list(map(int,input().split(" ")))
ans_array=[]
#符号の統一
add=0
mode=0
if min(nums)>0: #全部正の場合
    mode=0
elif max(nums)<0: #全部負の場合
    mode=1
elif max(nums)==min(nums)==0: #全部0
    print("0")
    sys.exit()
else: #正負混合
    mode=2
count=0

if mode==2: #need to modify
    temp=[]
    if abs(max(nums))<abs(min(nums)):
        mode=1 #全部負にする
        add=min(nums)
        ind=np.argmin(nums)
    elif abs(max(nums))>abs(min(nums)):
        mode=0
        add=max(nums)
        ind=np.argmax(nums)
    for i in range(len(nums)):
        nums[i]+=add
        ans_array.append("{0} {1}".format(ind+1,i+1))
        count+=1
        
        

if mode==0: #全部正
    for i in range(len(nums)-1):
        nums[i+1]+=nums[i]
        count+=1
        ans_array.append("{0} {1}".format(i+1,i+2))
    print(count)
    for i in ans_array:
       print(i)
                

elif mode==1:
    nums.reverse()
    for i in range(len(nums)-1):
        nums[i+1]+=nums[i]
        count+=1    
        ans_array.append("{0} {1}".format(i+1,i+2))

    print(count)

    print(ans)
    


### FIXED CODE ###

import sys
import numpy as np
N=int(input())
nums=list(map(int,input().split(" ")))
ans_array=[]
#符号の統一
add=0
mode=0
if min(nums)>0: #全部正の場合
    mode=0
elif max(nums)<0: #全部負の場合
    mode=1
elif max(nums)==min(nums)==0: #全部0
    print("0")
    sys.exit()
else: #正負混合
    mode=2
count=0

if mode==2: #need to modify
    temp=[]
    if abs(max(nums))<abs(min(nums)):
        mode=1 #全部負にする
        add=min(nums)
        ind=np.argmin(nums)
    elif abs(max(nums))>=abs(min(nums)):
        mode=0
        add=max(nums)
        ind=np.argmax(nums)
    for i in range(len(nums)):
        nums[i]+=add
        ans_array.append("{0} {1}".format(ind+1,i+1))
        count+=1
        
        

if mode==0: #全部正
    for i in range(len(nums)-1):
        nums[i+1]+=nums[i]
        count+=1
        ans_array.append("{0} {1}".format(i+1,i+2))
    print(count)
    for i in ans_array:
       print(i)
                

elif mode==1:
    nums.reverse()
    for i in range(len(nums)-1):
        nums[i+1]+=nums[i]
        count+=1    
        ans_array.append("{0} {1}".format(len(nums)-i,len(nums)-i-1))

    print(count)
    for i in ans_array:
       print(i)
case=0
while True:
    case+=1
    W=input()
    if W==0:break
    print "Case {}:".format(case)
    dp=[0]*1000
    w=[0]*1000
    v=[0]*1000
    n=input()
    for i in xrange(n):
        v[i],w[i]=map(int,raw_input().strip().split(","))
    for i in xrange(n):
        for j in xrange(W,-1,-1):
            if j+w[i]<=W:
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i])
    print max(dp)
    print dp.index(max(dp))

### FIXED CODE ###

case=0
while True:
    case+=1
    W=input()
    if W==0:break
    print "Case {}:".format(case)
    dp=[0]*1001
    w=[0]*1001
    v=[0]*1001
    n=input()
    for i in xrange(n):
        v[i],w[i]=map(int,raw_input().strip().split(","))
    for i in xrange(n):
        for j in xrange(W,-1,-1):
            if j+w[i]<=W:
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i])
    print max(dp)
    print dp.index(max(dp))
from collections import defaultdict
n , k = map(int , input().split())
arr = list(map(int , input().split()))
dic = defaultdict(int)
for i in range(1,n+1):
	dic[i] = arr[i-1]
cycle = []
def dfs(node):
	if node in cycle:
		return node
	else:
		cycle.append(node)
		k = dfs(dic[node])
	return k
cyind = dfs(1)
#print(cycle, cyind)
csize = len(arr[cyind:])
k -= cyind - 1
k %= csize
count = 0
curr = 1
#print("k " , k)
while count != k:
	curr = dic[curr]
	count+=1
print(curr)



### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
n , k = map(int , input().split())
arr = list(map(int , input().split()))
dic = defaultdict(int)
for i in range(1,n+1):
	dic[i] = arr[i-1]
cycle = []
visited = [False]*(10**6)
curr = 1
while True:
	cycle.append(curr)
	visited[curr] = True
	curr = dic[curr]
	#k -= 1
	if visited[curr]:
		break

csize = 0
ind = 0
for i in range(len(cycle)-1,-1,-1):
	if cycle[i] == curr:
		ind = i + 1
		break
	csize += 1
offset = len(cycle) - csize - 1
#print(cycle,csize+1, k , curr,offset)
if k - offset < 0:
	exit(print(cycle[k]))
k -= offset
k %= csize + 1
print(cycle[offset + k])
a, b = map(int, input().split())

if a > b:
    print("a > b")
elif a == b:
    print("a == b")
else
    print("a < b")


### FIXED CODE ###

s=input().split()
a=int(s[0])
b=int(s[1])

if a > b:
    print("a > b")
elif a == b:
    print("a == b")
else:
    print("a < b")
c=[]
for i in range(3):
  a,b=map(int,input().split())
  c.append(a)
  c.append(b)
c=sorted(c)
if c[5]=c[3]:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

c=[]
for i in range(3):
  a,b=map(int,input().split())
  c.append(a)
  c.append(b)
c=sorted(c)
ans='YES'
for j in range(1,5):
  cnt=0
  for i in range(6):
    if c[i]==j:
      cnt+=1
  if cnt>2:
    ans='NO'
    break

print(ans)
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(M)]


for i in range(1000):
    t = str(i)
    if len(t) != N:
        continue
    flg=True
    for item in arr:
        if t[item[0]-1] != str(item[i]):
            flg=False
            break

    if flg:
        print(i)
        exit()

print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(M)]

for i in range(1000):
    s = str(i)
    if len(s) != N:
        continue

    flg = True
    for j in range(len(arr)):
        if s[arr[j][0]-1] != str(arr[j][1]):
            flg = False
            break

    if flg:
        print(i)
        exit()

print(-1)
t,x=map(int,input().split()))
print(t/x)


### FIXED CODE ###

t,x=map(int,input().split())
print(t/x)
n = int(input())
p = list(map(int,input().split()))
ans = 0
for i in range(n):
    if p[i]-1 == i:
        p[i], p[i+1] = p[i+1],p[i]
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    if a[i] == i+1:
        a[i], a[i+1] = a[i+1], a[i]
        ans += 1
if a[-1] == n:
    ans += 1
print(ans)
W,H,N=map(int,input().split())
x=[0]*N
y=[0]*N
a=[0]*N
minX=0
maxX=W
minY=0
maxY=H
for i in range(N):
  x[i],y[i],a[i]=map(int,input().split())
  if a[i]==1:
    minX=max(minX,x[i])
  if a[i]==2:
    maxX=min(maxX,x[i]) 
  if a[i]==3:
    minY=max(minY,y[i])
  if a[i]==4:
    maxY=min(maxY,y[i]) 

ans=(maxX-minX)*(maxY-minY)
if maxX<minX or maxY<minY:
  ans=0
print(max(ans)


### FIXED CODE ###

w,h,n=map(int,input().split())
a1,a2,a3,a4=0,w,0,h
for i in range(n):
    x,y,a=map(int,input().split())
    if a==1:
        a1=max(a1,x)
    elif a==2:
        a2=min(a2,x)
    elif a==3:
        a3=max(a3,y)
    else:
        a4=min(a4,y)
print(max(a2-a1,0)*max(a4-a3,0))
A,B,C = map(int, input().split())

a = A % B

if C % a == 0 or a % C == 0:
  print("YES")
else:
  print("NO")


### FIXED CODE ###

A,B,C = map(int, input().split())

for i in range(0,B):
  if (A*(i+1)) % B == C:
    print("YES")
    exit()

print("NO")
import sys


def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2: 
        return True    

    # all other even numbers are not primes
    if not n & 1: 
        return False

    # range starts with 3 and only needs to go up 
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True


max = sys.stdin.readline()
answer = []

for x in range(max):
    n = sys.stdin.readline()
    if isprime(n):
        answer.append(n)

print(' '.join(answer))

### FIXED CODE ###

import sys


def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2: 
        return True    

    # all other even numbers are not primes
    if not n & 1: 
        return False

    # range starts with 3 and only needs to go up 
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True


max = int(sys.stdin.readline())
answer = 0

for x in range(max):
    n = sys.stdin.readline()
    if isprime(int(n)):
        answer += 1

print(answer)
n=int(input())
c=0
for i in range(1,n+1,2):
  count=0
  for j in range(1,i**0.5):
    if i%j==0:
      count+=1
  if count==8:
    c+=1
print(c)

### FIXED CODE ###

n=int(input())
c=0
for i in range(1,n+1,2):
  count=0
  for j in range(1,i+1):
    if i%j==0:
      count+=1
  if count==8:
    c+=1
print(c)
MAX = 10**9

n, k = map(int, input().split())
cost = list(map(int, input().split()))
dp = [MAX] * (n)
dp[0] = 0

for i in range(1, n):
    for j in range(max(0, i-k), i+1):
                dp[i] = min(dp[i] ,dp[j] + abs(cost[i] - cost[j]))

print(dp[-1])


### FIXED CODE ###

def jump(i):
    memo[0] = 0
    memo[1] = abs(arr[1]- arr[0])               
    for i in range(2, n):
        memo[i] = min(memo[i-1] + abs(arr[i-1]- arr[i]) ,
                      memo[i-2] + abs(arr[i-2]- arr[i]))
    return memo[-1]    

n = int(input())
arr = list(map(int, input().split()))
memo = [-1] * n 
                   
result = jump(n)
print(result)
x=input()
if x=0:
  print(1)
else:
  print(0)

### FIXED CODE ###

x=int(input())
if x==0:
  print(1)
else:
  print(0)
import sys
 
while True:
    h, w = [ int( val ) for val in sys.stdin.readline().split( " " ) ]
    if 0 ==h and 0 == w:
        break
    pa = [ "#", "." ]
    d = 0
    ouput = []
    for i in range( h ):
        d = i&1
        for j in range( w ):
            ouput.append( pa[d] )
            d = not d   
        ouput.append( "\n" )    
    print( "".join( ouput ) )

### FIXED CODE ###

import sys
 
while True:
    h, w = [ int( val ) for val in sys.stdin.readline().split( " " ) ]
    if 0 ==h and 0 == w:
        break
    pa = [ "#", "." ]
    ouput = []
    for i in range( h ):
        for j in range( w ):
            ouput.append( pa[(i+j)&1] ) 
        ouput.append( "\n" )    
    print( "".join( ouput ) )