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

import sys
readline = sys.stdin.readline

DEBUG = False
table = [1, 1, 0, 0, 1, 0, 1, 0, 1, 0]
def query(A):
    if DEBUG:
        return True if sum(table[a] for a in A) > N//2 else False
    print('?', *[1+a for a in A])
    return True if readline().strip() == 'Red' else False

if DEBUG:
    N = len(table)//2
else:   
    N = int(readline())

zans = query(list(range(N)))
ok = 0
ng = N

while abs(ok-ng) > 1:
    med = (ok+ng)//2
    if query(list(range(med, med+N))) == zans:
        ok = med
    else:
        ng = med

tool1 = list(range(ok+1, ok+N))
st1 = set(tool1)
col = [None]*(2*N)

for i in range(2*N):
    if i in tool1:
        continue
    col[i] = query([i] + tool1)

cr = 0
cb = 0
tool2 = []
for i in range(2*N):
    if col[i] is None:
        continue
    if col[i]:
        if cr < N//2:
            cr += 1
            tool2.append(i)
    else:
        if cb < N//2:
            cb += 1
            tool2.append(i)

for i in tool1:
    col[i] = query(tool2 + [i])

print(''.join(['R' if col[i] else 'B' for i in range(2*N)]))



### FIXED CODE ###

import sys

def query(A):
    print(*(['?'] + sorted([1+a for a in A])), flush = True)
    return True if input().strip() == 'Red' else False

N = int(input())

zans = query(list(range(N)))
ok = 0
ng = N

while abs(ok-ng) > 1:
    med = (ok+ng)//2
    if query(list(range(med, med+N))) == zans:
        ok = med
    else:
        ng = med

tool1 = list(range(ok+1, ok+N))
st1 = set(tool1)
col = [None]*(2*N)

for i in range(2*N):
    if i in tool1:
        continue
    col[i] = query([i] + tool1)

cr = 0
cb = 0
tool2 = []
for i in range(2*N):
    if col[i] is None:
        continue
    if col[i]:
        if cr < N//2:
            cr += 1
            tool2.append(i)
    else:
        if cb < N//2:
            cb += 1
            tool2.append(i)

for i in tool1:
    col[i] = query(tool2 + [i])

print(''.join(['! '] + ['R' if col[i] else 'B' for i in range(2*N)]), flush = True)
### BUGGY CODE ###

import re
s = input()

pat = re.compile('ABC')
count = 0

while True:
    st = pat.search(s)
    if st:
        s = s.replace('ABC', 'BCA', 1)
        count += 1
    else:
        break

print(count)

### FIXED CODE ###

s = input()

count = 0
pre = ''
movable = 0
for i in reversed(s):
    if pre == '':
        pre = i
    elif pre == 'CB' and i == 'A':
        count += movable
    elif pre == 'CB' and i == 'C':
        pre = 'C'    
    elif pre == 'C' and i == 'B':
        movable += 1
        pre = 'CB'
    else:
        movable = 0
        pre = i   
print(count)
### BUGGY CODE ###

inp = input().split(" ")
N = int(inp[0])
K = int(inp[1])

arr = {}
keys = []

def bin_insert(arr, n, lo, hi):
	if lo == hi:
		return arr[:lo] + [n] + arr[lo:]
	mid = (hi+lo) // 2
	if n > arr[mid]:
		return bin_insert(arr, n, mid+1, hi)
	else:
		return bin_insert(arr, n, lo, mid)
	

for i in range(N):
	inp = input().split(" ")
	a = int(inp[0])
	b = int(inp[1])
	if a in arr:
		arr[a] += b
	else:
		arr[a] = b
		keys = bin_insert(keys, a, 0, len(keys))

for i in keys:
	K -= arr[i]
	if K <= 0:
		print(i)
		break

### FIXED CODE ###

nk = input().split(' ')
n = int(nk[0])
k = int(nk[1])

arr = []

for i in range(0, n):
	ab = input().split(' ')
	arr.append((int(ab[0]), int(ab[1])))

arr = sorted(arr)

pos = 0
while True:
	if k > arr[pos][1]:
		k -= arr[pos][1]
	else:
		print(arr[pos][0])
		break
	pos += 1
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
  ans += i
print(ans)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
d = {x:As.count(x) for x in set(As)}
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  if C in d:
    d[C] += B
  else:
    d[C] = B
res = 0
rest = N
for _ in range(N):
  m = max(d.keys())
  if rest < d[m]:
    res += rest*m
    break
  else:
    res += d[m]*m
    rest -= d[m]
    del d[m]
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
d = {}
for x in As:
  if x in d:
    d[x] += 1
  else:
    d[x] = 1
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  if C in d:
    d[C] += B
  else:
    d[C] = B
res = 0
rest = N
d2 = sorted([x for x in d.keys()],reverse=True)
for m in d2:
  x = d[m]
  if rest < x:
    res += rest*m
    break
  else:
    res += x*m
    rest -= x
print(res)
### BUGGY CODE ###

s = input()
end = "ABC"
while True:
  if s == end:
    print("Yes")
    break
  s = s.replace("ABC", "X")
  if ("A" in s) + ("B" in s) + ("C" in s) != 2:
    print("No")
    break

  for c in "ABC":
    if c not in s:
      s = s.replace("X", c)
      break


### FIXED CODE ###

s = input()
end = "ABC"
while True:
  if s == end:
    print("Yes")
    break
  s = s.replace(end, "X")
  if ("X" not in s) or sum((c in s for c in end)) != 2:
    print("No")
    break
  for c in end:
    if c not in s:
      s = s.replace("X", c)
      break
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    A, B, C = map(int, input().split())
    K = int(input())

    answer = "No"
    while K >= 1:
        if A>=B:
            B *= 2
            K -= 1
        elif B>=C:
            C *= 2
            K -= 1
    if A<B and B<C:
        answer = "Yes"
    print(answer)

if __name__ == "__main__":
    main()



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    A, B, C = map(int, input().split())
    K = int(input())

    answer = "No"
    for i in range(K):
        if A>=B:
            B *= 2
        elif B>=C:
            C *= 2
    if A<B and B<C:
        answer = "Yes"
    print(answer)

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

import numpy
H,W = (int(x) for x in input().split())

S_arr_arr = [[1]*(W+2)]
for i in range(H):
    S_arr_arr.append([0 if s=="." else 1 for s in "#"+input()+"#"])
S_arr_arr.append([1]*(W+2))
W_arr_arr = [[0]*(W+2) for _ in range(H+2)]

S_arr_arr = numpy.array(S_arr_arr)
W_arr_arr = numpy.zeros_like(S_arr_arr)

for j in range(H+2):
    i_begin = 0
    for i in range(W+2):
        if S_arr_arr[j,i] == 1:
            for ix in range(i_begin+1, i):
                W_arr_arr[j,ix] += i-i_begin-1
            i_begin = i
for i in range(W+2):
    j_begin = 0
    for j in range(H+2):
        if S_arr_arr[j,i] == 1:
            for jx in range(j_begin+1, j):
                W_arr_arr[jx,i] += j-j_begin-1
            j_begin = j

max_ans = max([max(W_arr) for W_arr in W_arr_arr]) - 1

print(max_ans)


### FIXED CODE ###

H,W = (int(x) for x in input().split())

S_arr_arr = [[1]*(W+2)]
for i in range(H):
    S_arr_arr.append([0 if s=="." else 1 for s in "#"+input()+"#"])
S_arr_arr.append([1]*(W+2))

W_arr_arr = [[0]*(W+2) for _ in range(H+2)]
for j in range(H+2):
    i_begin = 0
    for i in range(W+2):
        if S_arr_arr[j][i] == 1:
            for ix in range(i_begin+1, i):
                W_arr_arr[j][ix] += i-i_begin-1
            i_begin = i
for i in range(W+2):
    j_begin = 0
    for j in range(H+2):
        if S_arr_arr[j][i] == 1:
            for jx in range(j_begin+1, j):
                W_arr_arr[jx][i] += j-j_begin-1
            j_begin = j

max_ans = max([max(W_arr) for W_arr in W_arr_arr]) - 1

print(max_ans)
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
import math
## 素数判定 O (√n)
def is_prime(n):
    for i in range(2,int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
    return n != 1 # 1の場合は除外
def soinsu(n):
    dic = defaultdict(int)
    i = 2
    while i*i <= n:
        if n%i == 0:
            dic[i] += 1
            n //= i
        else:
            i += 1
    if n!= 1:
        dic[n] += 1
    return dic
n = I()
ans = 0
yaku = [1] *(10**7+1)
yaku[0] = 0
yaku[1] = 1
for i in range(2,10**7+1):
    if i > n:
        break
    for j in range(i*2,10**7+1,i):
        if j > n:
            break
        yaku[j] += 1
for i in range(2,n+1):
    if is_prime(i):
        y = 2
    else:
        y = yaku[i]+1
    ans += i * y
print(ans+1)


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
import math
## 素数判定 O (√n)

n = I()
ans = 0
yaku = [1] *(10**7+1)
yaku[0] = 0
yaku[1] = 1
for i in range(1,n+1):
    for j in range(i*2,n+1,i):
        yaku[j] += 1
for i in range(1,n+1):
    y = yaku[i]
    ans += i * y
print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())
mn = 10**10
cal = 0
for i in range(L,R+1):
    for j in range(i+1,R+1):
        
        cal = (i%2019*j%2019)%2019
        if cal < mn:
            mn = cal
            
print(mn)
        

### FIXED CODE ###

L,R = map(int,input().split())
mn = 10**10
cal = 0
for i in range(L,R+1):
    for j in range(i+1,R+1):
        
        cal = ((i%2019)*(j%2019))%2019
        if cal < mn:
            mn = cal
        if cal == 0:
            break
    else:
        continue
    break
print(mn)
### BUGGY CODE ###

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

ans = 3 * 10**5

for i in range(n):
    ans = min(ans, s[:i].count('W') + s[i+1:].count('E'))

print(ans)

### FIXED CODE ###

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

ans = 3 * 10**7
w = [0]
e = [0]

for i, a in enumerate(s):
    if a == 'W':
        w.append(w[-1]+1)
    else:
        w.append(w[-1])

for i, a in enumerate(s[::-1]):
    if a == 'E':
        e.append(e[-1]+1)
    else:
        e.append(e[-1])

e.reverse()

for i in range(n):
    ans = min(ans, w[i]+e[i+1])

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

from collections import deque
import itertools

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    if cost > dist[h][w] and dist[h][w] != -1:
        continue
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh, dw in itertools.product(range(-2, 3), range(-2, 3)):
        if check_appnendable(h+dh, w+dw, cost+1):
            d.appendleft([h+dh, w+dw, cost+1])
            dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-1])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[float("inf") for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

if dist[D_h-1][D_w-1] < float("inf"):
    print(dist[D_h-1][D_w-1])
else:
    print(-1)
### BUGGY CODE ###

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

for i in range(n):
  a[i] = [(-1) * a[i], (-1) * a[i], 1]

import heapq
heapq.heapify(a)

for _ in range(k):
  i = heapq.heappop(a)
  i[2] += 1
  i[0] = i[1] / i[2]
  heapq.heappush(a, i)

from math import ceil
print(ceil((-1) * heapq.heappop(a)[0]))

### FIXED CODE ###

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

# binary search
left = 1
right = 10 ** 9

while left < right:
    center = (left + right) // 2

    total = 0
    for i in a:
        if i % center == 0:
            i -= 1
        total += i//center
    
    if total > k:
        left = center + 1
    else:
        right = center

print(left)
### BUGGY CODE ###

n = int(input())
l = [int(input()) for i in range(n)]

for i in range(n):
    ll = l[0:i] + l[i+1:]
    print(max(ll))

### FIXED CODE ###

n = int(input())
l = [int(input()) for i in range(n)]
ll = sorted(l, reverse = True)
m1 = ll[0]
m2 = ll[1]

for i in range(n):
    if l[i] == m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

N = int(input()) 
A=list(map(int,input().split())) 
i=0 
s=[]
sumall=0
while sumall<N-1: 
    s.append(0) 
    s[i]=A.count(i+1)
    sumall=sumall+s[i]
    print(s[i])
    i=i+1       
for _ in range(i,N):
    print(0)

### FIXED CODE ###

import collections
n = int(input())
base = map(int,input().split())
c = collections.Counter(base)
for i in range(1,n):
    print(c[i])
print(0)
### BUGGY CODE ###



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

def get_key(l):
    return ','.join(map(str, l))

def calc(l):
    if len(l) <= 1:
        dp[get_key(l)] = 0
        return 0

#    print(l)
    x = abs(l[0]-l[1]) + calc(l[1:])
    dp[get_key(l)] = x
    return x

# 0 3 5 -1 0 みたいに
L = [0] + A + [0]
dp = {}
for i in range(1, N+1):
    l = L[0:i] + L[i+1:]
    print(calc(l))

### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

def calc(l):
    count = 0
    for i in range(len(l)-1):
        count += abs(l[i]-l[i+1])

    return count

# 0 3 5 -1 0 みたいに
L = [0] + A + [0]
max_L = calc(L)
#print(max_L)

# 左右引いて、左右通しで計算すればいい
for i in range(1, N+1):
    diff_minus = abs(L[i-1]-L[i])+abs(L[i]-L[i+1])
    diff_plus = abs(L[i-1]-L[i+1])
    print(max_L-diff_minus+diff_plus)
### BUGGY CODE ###

n = int(input())

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

for i in range(n):
    print(str(a.index(i+1)+1) + " ",end = "")


### FIXED CODE ###

n = int(input())

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

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

print(" ".join(map(str,b)))
### BUGGY CODE ###


d={}

n,k=map(int,input().split(" "))
flag=True
while(flag):

    if(abs(n-k) not in d.keys()):
        d[abs(n-k)]=True
        n=abs(n-k)
    else:
        flag=False
#print(d.keys())
print(min(d.keys()))



### FIXED CODE ###

n,k=map(int,input().split(" "))

if(n==k or n%k==0):
    print(0)
elif(n<k):
    print(min(n,abs(n-k)))
else:
    q=n//k
    ma=n%k

    aa = n-q*k
    print(min(aa,abs(aa-k)))
### BUGGY CODE ###

import functools
import math
import fractions
N = int(input())
a = list(map(int, input().split()))
 
gcd = []
for i in range(N):
    list_not_i = a.copy()
    list_not_i.remove(a[i])
    gcd.append(functools.reduce(fractions.gcd, list_not_i))
 
print(max(gcd))

### FIXED CODE ###

import functools
import fractions
N = int(input())
a = list(map(int, input().split()))

L = [0] * N
for i in range(N) :
        if i == 0 :
                L[0] = 0
        elif i == 1 :
                L[1] = a[0]
        else :
                L[i] = fractions.gcd(L[i-1], a[i-1])

a.reverse()
R = [0] * N
for i in range(N) :
        if i == 0 :
                R[0] = 0
        elif i == 1 :
                R[1] = a[0]
        else :
                R[i] = fractions.gcd(R[i-1], a[i-1])
R.reverse()
a.reverse()

gcd = [0] * N
for i in range(N) :
        if i == 0 :
                gcd[0] = R[0]
        elif i == N-1 :
                gcd[N-1] = L[N-1]
        else :
                gcd[i] = fractions.gcd(L[i],R[i])

print(max(gcd))
### BUGGY CODE ###

from heapq import *
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append([q,r])
    a[q].append([p,r])
    b[p].append([q,g])
    b[q].append([p,g])
def f(x,r):
    p=[float("INF")]*(n+1)
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p[1:]
s1,t1=f(s,a),f(t,b)
p=[]
for i in range(n):
    p.append((s1[i]+t1[i],i+1))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])

### FIXED CODE ###

from heapq import heappush,heappop
n,m,s,t=map(int,input().split())
a,b=[[]for i in range (n+1)],[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=(int(i) for i in input().split())
    a[p].append((q,r))
    a[q].append((p,r))
    b[p].append((q,g))
    b[q].append((p,g))
def f(x,r):
    p=[float("inf")for i in range(n+1)]
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p
s1,t1,p=f(s,a),f(t,b),[]
for i in range(1,n+1):
    p.append((s1[i]+t1[i],i))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4017206
# N,M = map(int, input().split())
N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))


#1,2,3
A,B,C = (a[i] for i in range(1,4))

# dpA,B,C

dp = [ [ [0] * (C+1) 
           for _ in range(B+C+1)
       ]
           for _ in range(A+B+C+1) 
     ]


for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            # print("a: {}, b: {}, c:{} ".format(a,b,c), end = " ")
            if a == b == c == 0:
                # print("")
                continue

            dp[a][b][c] = (
                    ( a * ( dp[a-1][b][c]   if a else 0)  ) + 
                    ( b * ( dp[a+1][b-1][c] if b else 0)  ) +
                    ( c * ( dp[a][b+1][c-1] if c else 0)  ) + N 
                   ) / ( a+b+c ) 
            # print(dp[a][b][c])

print(dp[A][B][C])


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4017206
# N,M = map(int, input().split())
N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))


#1,2,3
A,B,C = (a[i] for i in range(1,4))

# dpA,B,C

# dp = [ [ [0] * (C+1) 
#            for _ in range(B+C+1)
#        ]
#            for _ in range(A+B+C+1) 
#      ]

dp = [ [ [0]*(A+B+C+1) for _ in range(B+C+1)]
        for _ in range(C+1) ] 

for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            # if a == b == c == 0:
            #     continue

            try: 
                dp[c][b][a] = (
                        ( a * ( dp[c][b][a-1]   if a else 0)  ) + 
                        ( b * ( dp[c][b-1][a+1] if b else 0)  ) +
                        ( c * ( dp[c-1][b+1][a] if c else 0)  ) + N 
                       ) / ( a+b+c ) 
                # dp[a][b][c] = (
                #         ( a * ( dp[a-1][b][c]   if a else 0)  ) + 
                #         ( b * ( dp[a+1][b-1][c] if b else 0)  ) +
                #         ( c * ( dp[a][b+1][c-1] if c else 0)  ) + N 
                #        ) / ( a+b+c ) 
            except:
                continue

print(dp[C][B][A])
# print(dp[A][B][C])
### BUGGY CODE ###

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

N = INT()

import itertools
import collections

alphabet = 'abcdefghijklmnopqrstuvwxyz'

a_set = set()
for w in itertools.product(range(N), repeat=N):
    # print(w, end=", ")
    seen = {}

    i = 0
    for l in w:
        if l not in seen.keys():
            seen[l] = i
            i += 1

    # print(seen, end="")

    ans = [0] * N

    for i in range(len(ans)):
        ans[i] = seen[w[i]]

    if tuple(ans) not in a_set:
        print("".join([alphabet[i] for i in ans]))
        a_set.add(tuple(ans))






### FIXED CODE ###

# https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d

N = int(input())

alphabet = "abcdefghijklmnopqrstuvwxyz"

curr_str = []

def print_str(curr_str):
    string = ""
    for i in curr_str:
        string += alphabet[i]
    print(string)


def dfs(index, curr_str, curr_char):
    if curr_char > index:
        return None
    if curr_char > max(curr_str) + 1:
        return None

    if index == N-1:
        print_str(curr_str + [curr_char])
        return None

    for i in range(N):
        dfs(index+1, curr_str+[curr_char], i)


if N == 1:
    print("a")
else:    
    for i in range(N):
        dfs(1, [0], i)
### BUGGY CODE ###

ht, st, ha, sa = list(map(int, input().split(' ')))
bool_player = True  # Takashi
while (not(ht <= 0) or not(st <= 0)):
    if bool_player:
        ha -= st
        bool_player = False
    else:
        ht -= sa
        bool_player = True

if ht <= 0:
    print('No')
else:
    print('Yes')


### FIXED CODE ###

ht, st, ha, sa = list(map(int, input().split(' ')))
bool_player = True  # Takashi
while (ht > 0 and ha > 0):
    if bool_player:
        ha -= st
        bool_player = False
    else:
        ht -= sa
        bool_player = True

if ht <= 0:
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

n = 50001
c = [1 for i in range(n)]
c[0] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j <= n:
        c[j - 1] = 0
        j += i
    i += 1

while True:
    n = int(input())
    if n == 0:
        break
    elif n%2 == 1:
        print(0)
        continue
    cnt = 0
    for i in range(n//2):
        if c[i] == 1 and c[n-i] == 1:
            cnt +=1
    print(cnt)



### FIXED CODE ###

n = 50001
is_prime = [i for i in range(n)]
is_prime[0] = is_prime[1] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = 0
        j += i
    i += 1

prime_set  = set(is_prime)
prime_set.remove(0)
prime_list = sorted(list(prime_set))

while True:
    cnt = 0
    n = int(input())
    if n == 0:
        break
    for i in prime_list:
        if i > n//2:
            break
        if n - i in prime_set:
            cnt += 1
    print(cnt)