CodeEff/ECCO huggingface dataset:
# Original solution
N = int(eval(input()))
ai = list(map(int, input().split()))

box = [0] * N
v = N // 2  # 後半部の最初のindex

for i in range(v, N):
    if ai[i] == 0:
        box[i] = 0
    else:
        box[i] = 1

for i in range(v - 1, -1, -1):
    s = [ai[x] == 1 for x in range(i + 1, N) if (x + 1) % (i + 1) == 0]
    cnt = s.count(True)
    if cnt & 1 == 1:
        box[i] = 0 if ai[i] & 1 == 1 else 1
    else:
        box[i] = 0 if ai[i] & 1 == 0 else 1

print((box.count(1)))
for x in box:
    if x == 1:
        print(x)


# Optimized solution
N = int(eval(input()))
ai = list(map(int, input().split()))

box = [0] * N
v = N // 2  # 後半部の最初のindex

for i in range(v, N):
    if ai[i] == 0:
        box[i] = 0
    else:
        box[i] = 1

for i in range(v - 1, -1, -1):
    value = i + 1
    sum = 0
    for j in range(value * 2 - 1, N, value):
        sum += box[j]
    if sum & 1 == 1:
        box[i] = 0 if ai[i] & 1 == 1 else 1
    else:
        box[i] = 0 if ai[i] & 1 == 0 else 1
print((box.count(1)))
for i in range(N):
    if box[i] == 1:
        print((i + 1))
# Original solution
import sys 
input = sys.stdin.readline

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

#box = [0]*(N+1)

for i in range(N,0,-1):
    k=2
    temp=a[i-1]
    #print(123,i,ball)
    while i*k<=N:
        if a[i*k-1]==1:
            temp = (temp+1)%2
        k+=1
    a[i-1] = temp
#print(box)
M=0
b=[]
for i in range(1,N+1):
    if a[i-1]==1:
        M+=1
        b.append(i)

print(M)
[print(x) for x in b]


# Optimized solution
import sys 
input = sys.stdin.readline

N = int(input())
a = list(map(int,input().split()))
a.insert(0,-1)

for i in range(N,0,-1):
    k=2
    temp=a[i]
    while i*k<=N:
        if a[i*k]==1:
            temp = (temp+1)%2
        k+=1
    a[i] = temp

M=0
b=[]
for i in range(1,N+1):
    if a[i]==1:
        M+=1
        b.append(i)

print(M)
[print(x) for x in b]
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
res = [0 for i in range(n)]
lres = []
for i in range(n,0,-1):
    l = []
    flag = 0
    t = i*2
    while t <= n:
        flag = flag ^ res[t-1]
        t = t+i
    if a[i-1] != flag:
        res[i-1] = 1
        lres.append(str(i))

print((len(lres)))
if len(lres) != 0:
    print((" ".join(lres)))
 

# Optimized solution
def main():
    n = int(eval(input()))
    a = list(map(int,input().split()))
    res = [0 for i in range(n)]
    lres = []
    for i in range(n,0,-1):
        l = []
        flag = 0
        t = i*2
        while t <= n:
            flag = flag ^ res[t-1]
            t = t+i
        if a[i-1] != flag:
            res[i-1] = 1
            lres.append(str(i))

    print((len(lres)))
    if len(lres) != 0:
        print((" ".join(lres)))

main()
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))


def returnResMod2(i):
    # i+1の倍数の箱のaiの和の剰余を求める
    res = sum([ansList[k] for k in range(N) if (k+1) % (i+1) == 0]) % 2
    return res


ansList = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = (returnResMod2(i)+A[i]) % 2
    ansList[i] = tmp


M = sum(ansList)
print(M)
if M == 0:
    quit()
print((' '.join([str(i+1) for i, a in enumerate(ansList) if a == 1])))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))


def returnResMod2(i):
    # i+1の倍数の箱のaiの和の剰余を求める
    res = sum([ansList[(i+1)*(k+1)-1] for k in range(N//(i+1))]) % 2
    return res


ansList = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = (returnResMod2(i)+A[i]) % 2
    ansList[i] = tmp
    

M = sum(ansList)
print(M)
if M == 0:
    quit()
print((' '.join([str(i+1) for i, a in enumerate(ansList) if a == 1])))
# Original solution
l = []
counter = 0
ans_list = []

n = int(eval(input()))
b_list = [0 for _ in range(n)]
l = list(map(int, input().split()))

for i in range(n,0,-1):
    index = n // i
    if index == 1: # 倍数がないとき
        b_list[i-1] = l[i-1]
    else:
        sum = 0
        for j in range(2, index+1):
            sum = sum + b_list[(i * j)-1]
        #print(l[i-1], sum)
        if l[i-1] != sum % 2:
            b_list[i-1] = 1

    if b_list[i-1] == 1:
        counter += 1
        ans_list.append(str(i))

#print(ans_list)
print(counter)
if ans_list != []:
    print((' '.join(sorted(ans_list))))


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
ans_list = [0 for _ in range(n)]

for i in range(n-1, -1, -1):
    prev = 0
    index = i+1
    for j in range(2, n+1):
        if (index * j)-1 >= n: break
        prev += ans_list[(index * j)-1]
    if prev % 2 != a[i]:
        ans_list[i] = 1

print((sum(ans_list)))
if sum(ans_list) != 0:
    print((' '.join([str(i+1) for i, x in enumerate(ans_list) if x == 1])))
# Original solution
N = int(eval(input()))
ax = list(map(int,input().split()))
 

boxin = []
for cnt in range(N, 0, -1):
    a = ax[cnt-1]
    
    i = 2
    memo_cnt = 0
    while 1:
        test_val = i * cnt
        if test_val > N:
            break
        if test_val in boxin:
            memo_cnt += 1
        i += 1
    if a != memo_cnt % 2:
        boxin.append(cnt)

 
box = len(boxin)
print(box)
if box != 0:
    boxin.reverse()
    print((' '.join(map(str, boxin))))

# Optimized solution
N = int(eval(input()))
ax = list(map(int,input().split()))
 

boxin = []
bx = [0 for _ in range(N+1)]
for cnt in range(N, 0, -1):
    a = ax[cnt-1]
    i = 2
    memo_cnt = 0
    while 1:
        test_val = i * cnt
        if test_val > N:
            break
        if bx[test_val]:
            memo_cnt += 1
        i += 1
    if a != memo_cnt % 2:
        boxin.append(cnt)
        bx[cnt] = 1

 
box = len(boxin)
print(box)
if box != 0:
    boxin.reverse()
    print((' '.join(map(str, boxin))))
# Original solution
N = int(eval(input()))
A = [0]
A.extend(list(map(int, input().split())))

boxes = [0 for i in range(N+1)]  # 後に最初の要素を取り除く

for i in range(N, 0, -1):
    # print("iiii = ", i)
    wa = 0
    for j in range(i, N+1, i):
        # print("j = ", j)
        wa += boxes[j]
    if wa % 2 != A[i]:
        boxes[i] = 1

ans_n = sum(boxes)
ans_list = []

for i in range(len(A)):
    if boxes[i] == 1:
        ans_list.append(i)
print(ans_n)
if ans_n != 0:
    print((" ".join(map(str, ans_list))))


# Optimized solution
N = int(eval(input()))
A = [0]
A.extend(list(map(int, input().split())))
boxes = [0] * (N+1)

for i in range(N, 0, -1):
    # print(i)
    wa = 0
    for j in range(i, N+1, i):
        # print(j)
        wa += boxes[j]
    if wa % 2 != A[i]:
        boxes[i] = 1
    # print("hogeeeeeeeeee")
ans = []
for i in range(len(boxes)):
    if boxes[i] == 1:
        ans.append(i)

print((len(ans)))
if len(ans) != 0:
    print((" ".join(map(str, ans))))
# Original solution
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return list(map(int, sys.stdin.readline().split()))
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
A = li()

A_f = A[:N//2]
A_l = A[N//2:]

for i in reversed(list(range(N//2))):
    ind = i+1
    ind += i+1
    while(ind-1 < N):
        A[i] += A[ind-1]
        ind += i+1
    A[i] %= 2

#table += A_l

ans = ''
print((sum(A)))
for i in range(N):
    if A[i]%2 == 1:
        ans += str(i+1) + ' '

if ans != '':
    print((ans[:-1]))

# Optimized solution
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return list(map(int, sys.stdin.readline().split()))
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
A = li()

for i in reversed(list(range(N//2))):
    ind = i+1
    ind += i+1
    while(ind-1 < N):
        A[i] += A[ind-1]
        ind += i+1
    A[i] %= 2

'''
for i in range(N):
    ind = 2*(i+1)
    while(ind-1 < N):
        A[i] += A[ind-1]
        ind += i+1
    A[i] %= 2
'''

ans = ''
print((sum(A)))
for i in range(N):
    if A[i]%2 == 1:
        ans += str(i+1) + ' '

if ans != '':
    print((ans[:-1]))
# Original solution
# -*- coding: utf-8 -*-
N = int(eval(input()))
a_list = list(map(int, input().split()))

M = 0
box_dict = {}
for i in reversed(list(range(N))):
    idx = i + 1
    multi_sum = 0
    for key, value in list(box_dict.items()):
        if key % (idx * 2) == 0:
            multi_sum += value
    if a_list[i] - multi_sum == 0:
        box_dict[idx] = 0
    else:
        box_dict[idx] = 1
        M += 1

print(M)
if M > 0:
    b_list = [key for key, value in list(box_dict.items()) if value == 1]
    print((" ".join(map(str, b_list))))

# Optimized solution
# -*- coding: utf-8 -*-
N = int(eval(input()))
a_list = list(map(int, input().split()))

M = 0
box_dict = {}
for i in reversed(list(range(N))):
    idx = i + 1
    multi_sum = 0
    if N // idx < 2:
        if a_list[i] == 0:
            box_dict[idx] = 0
        else:
            box_dict[idx] = 1
            M += 1
    else:
        for j in range(2, (N // idx) + 1):
            multi_sum += box_dict[idx * j]
        if a_list[i] - (multi_sum % 2) == 0:
            box_dict[idx] = 0
        else:
            box_dict[idx] = 1
            M += 1

print(M)
if M > 0:
    b_list = [key for key, value in list(box_dict.items()) if value == 1]
    print((" ".join(map(str, b_list))))
# Original solution
import sys
import math

def add_ball(idx):
    add_list = []
    for j in range(1, int(math.sqrt(idx))+1):
        if idx%j == 0:
            add_list.append(j)
            if j != idx//j:
                add_list.append(idx//j)
    for k in add_list:
        b_list[k] += 1

if __name__ == "__main__":
    input = sys.stdin.readline

    n = int(eval(input()))
    a_list = list(map(int, input().split()))
    b_list = [0] * (n+1)
    ans_list = []
    for a, i in zip(reversed(a_list), list(range(n, 0, -1))):
        if a != b_list[i]%2:
            ans_list.append(i)
            add_ball(i)
    cnt = len(ans_list)
    ans_list.sort()
    print(cnt)
    if cnt > 0:
        print((' '.join(map(str, ans_list))))


# Optimized solution
import sys
import math

def add_ball(idx):
    add_list = []
    for j in range(1, int(math.sqrt(idx))+1):
        if idx%j == 0:
            add_list.append(j)
            if j != idx//j:
                add_list.append(idx//j)
    for k in add_list:
        b_list[k] += 1

if __name__ == "__main__":
    input = sys.stdin.readline

    n = int(eval(input()))
    a_list = list(map(int, input().split()))
    b_list = [0] * (n+1)
    cnt = 0
    ans_list = []
    for a, i in zip(reversed(a_list), list(range(n, 0, -1))):
        if a != b_list[i]%2:
            cnt += 1
            ans_list.append(i)
            add_ball(i)
    ans_list.sort()
    print(cnt)
    if cnt > 0:
        print((' '.join(map(str, ans_list))))
# Original solution
import collections
import heapq
n = int(input())
ais = [0] + list(map(int, input().split())) 
#print ais
res = [0 for __ in range(n +1)]
for u in range(n, 0, -1):
	c = u*2
	cumul = 0
	while(c <= n):
		cumul += res[c]
		c += u
	if ais[u] != (cumul % 2): 
		res[u] = 1
s = sum(res)
print(s)
if s:
	print(' '.join([str(i) for i in range(len(res)) if res[i] == 1]))

# Optimized solution
n = int(input())
ais,res = [0] + list(map(int, input().split())) ,[0 for _ in range(n +1)]
for u in range(n, 0, -1):
	c,cumul = u,0
	while(c <= n):
		cumul += res[c]
		c += u
	if ais[u] != (cumul % 2):  res[u] = 1
s = sum(res)
print(s)
if s: print(' '.join([str(i) for i in range(len(res)) if res[i] == 1]))
# Original solution
import sys
input=sys.stdin.readline
n=int(input())
l=tuple(map(int,input().split()))
ret=[]
ll=[0]*n
ans=0
for i in range(n,0,-1):
    s=l[i-1]
    for j in range(2,n//i+1):
        s-=ll[j*i-1]
        s%=2
    ll[i-1]=s
    ans+=s
    if s:ret.append(i)
print(ans)
if ans:print(*ret,sep=" ")


# Optimized solution

n=int(input())
l=tuple(map(int,input().split()))
ret=[]
ll=[0]*n
ans=0
for i in range(n,0,-1):
    s=l[i-1]
    for j in range(2,n//i+1):
        s-=ll[j*i-1]
        s%=2
    ll[i-1]=s
    ans+=s
    if s:ret.append(i)
print(ans)
if ans:print(*ret,sep=" ")
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
B=[0] * N
ans = []
for i in reversed(list(range(1, N+1))):
    a = A[i-1]
    for j in range(1, N+1):
        tmp = i * j
        if tmp > N:
            break
        a += B[tmp-1]
    if a % 2 == 1:
        ans.append(i)
    B[i-1] = a % 2
print((len(ans)))
for a in ans:
    print(a)

# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
ans = []
for i in reversed(list(range(1, N+1))):
    a = A[i-1]
    for j in range(2, N+1):
        tmp = i * j
        if tmp > N:
            break
        a += A[tmp-1]
    if a % 2 == 1:
        ans.append(i)
    A[i-1] = a % 2
print((len(ans)))
for a in ans:
    print(a)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
B=[0] * N
ans = []
for i in reversed(list(range(1, N+1))):
    a = 0
    for j in range(1, N+1):
        tmp = i * j
        if tmp > N:
            break
        a = (B[tmp-1] + a) % 2
    if (A[i-1] + a) % 2 == 1:
        ans.append(i)
    B[i-1] = (A[i-1] + a) % 2
print((len(ans)))
for a in ans: print(a)

# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
ans = []
for i in reversed(list(range(1, N+1))):
    a = A[i-1]
    for j in range(2, N+1):
        tmp = i * j
        if tmp > N:
            break
        a += A[tmp-1]
    if a % 2 == 1:
        ans.append(i)
    A[i-1] = a % 2
print((len(ans)))
for a in ans:
    print(a)
# Original solution
N = int(eval(input()))
A = [int(_) for _ in input().split()]

B = []
for i in range(1, N+1)[::-1]:
    a = A[i-1]
    v = len(list([x for x in B if x % i == 0]))
    if v % 2 != a:
        B.append(i)

for i in range(1, N+1)[::-1]:
    a = A[i-1]
    v = len(list([x for x in B if x % i == 0]))
    if v % 2 != a:
        print((-1))
        exit(0)

print((len(B)))
if B != []:
    print((" ".join([str(b) for b in B])))
    

# Optimized solution
N = int(eval(input()))
A = [int(_) for _ in input().split()]

X = [0 for _ in range(N)]
ans = []
for i in range(N)[::-1]:
    v = 0
    for j in range(i, N, i+1):
        v += X[j]
    if v % 2 != A[i]:
        X[i] = 1
        ans.append(i+1)

print((len(ans)))
for i in ans:
    print(i)
# Original solution
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 2  # type: int


import math
import collections


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


def solve(N: int, a: "List[int]"):
    b = [0]*N
    for i in range(N-1, -1, -1):
        if b[i] % MOD == a[i]:
            b[i] = 0
        else:
            b[i] = 1
            for d in make_divisors(i+1):
                if d != i+1:
                    b[d-1] += 1
    c = [i+1 for i, val in enumerate(b) if val % 2 > 0]
    print(len(c))
    if len(c) != 0:
        print(*c, sep=" ")
    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()


# Optimized solution
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 2  # type: int


import math
import collections


def solve(N: int, a: "List[int]"):
    b = [0]*N
    for i in range(N-1, -1, -1):
        tmp = 0
        for j in range(2, N//(i+1)+1):
            tmp += b[j*(i+1)-1]
        if tmp % MOD == a[i]:
            b[i] = 0
        else:
            b[i] = 1

    c = [i+1 for i, val in enumerate(b) if val % 2 > 0]
    print(len(c))
    if len(c) != 0:
        print(*c, sep=" ")
    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()
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = list(map(int, read().split()))

    B = [False] * (N + 1)

    for i, a in reversed(list(enumerate(A, 1))):
        tmp = 0
        for j in range(2 * i, N + 1, i):
            tmp ^= B[j]
        B[i] = a ^ tmp

    ans = [i for i in range(1, N + 1) if B[i]]
    print((len(ans)))
    if len(ans) > 0:
        print((' '.join(map(str, ans))))

    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = list(map(int, read().split()))

    B = [False] * (N + 1)

    for i, a in reversed(list(enumerate(A, 1))):
        tmp = 0
        for j in range(2 * i, N + 1, i):
            tmp += B[j]
        B[i] = tmp % 2 != a

    ans = [i for i in range(1, N + 1) if B[i]]
    print((len(ans)))
    if len(ans) > 0:
        print((' '.join(map(str, ans))))

    return


if __name__ == '__main__':
    main()
# Original solution
def main():
    N = int(eval(input()))
    A = [0] + list(map(int, input().split()))

    for i in range(N//2, 0, -1):
        sum_m = sum([A[j] for j in range(i*2, N+1) if j%i==0])
        if A[i] == 0:
            if sum_m % 2 == 1:
                A[i] = 1
        else:
            if sum_m % 2 == 1:
                A[i] = 0

    sum_b = sum(A)
    print(sum_b)
    if sum_b:
        for i in range(N+1):
            if A[i] == 1:
                print(i)


if __name__ == "__main__":
    main()

# Optimized solution
def main():
    N = int(eval(input()))
    A = [0] + list(map(int, input().split()))

    for i in range(N//2, 0, -1):
        sum_m = sum([A[i*j] for j in range(2, N//i+1)])
        if A[i] == 0:
            if sum_m % 2 == 1:
                A[i] = 1
        else:
            if sum_m % 2 == 1:
                A[i] = 0

    sum_b = sum(A)
    print(sum_b)
    if sum_b:
        ans = [str(i) for i, v in enumerate(A) if v == 1]
        print(('\n'.join(ans)))


if __name__ == "__main__":
    main()
# Original solution
from sys import stdin

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

point = 0
lin = []

for i in range(n,0,-1):
    score = 0
    for j in range(i+1,n+1):
        if j % i == 0:
            score += li[j-1]
    if li[i-1] != score%2:
        point += 1
        lin.append(i)

print(point)
for i in lin:
    print(i)

# Optimized solution
from sys import stdin

n = int(stdin.readline().rstrip())
li = [0] + list(map(int,stdin.readline().rstrip().split()))
lin = [0]*(n+1)
point = 0
lis = []

for i in range(n,0,-1):
    su = sum(lin[i::i])%2
    if li[i] != su:
        lin[i] = 1
        point += 1
        lis.append(i)
    
print(point)
lis.sort()

for i in lis:
    print(i)
# Original solution
n = 50001
is_prime = [True for i in range(n)]
is_prime[0] = is_prime[1] = False
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = False
        j += i
    i += 1

cnt_pair = [0 for i in range(n)]
for i in range(3, n//2, 2):
    if is_prime[i]:
        for j in range(i, n - i, 2):
           if is_prime[j]:
               cnt_pair[i + j] += 1

while True:
    n = int(eval(input()))
    if n == 0:
        break
    print((cnt_pair[n]))



# Optimized solution
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(eval(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)
# Original solution
def get_input():
    while True:
        try:
            yield ''.join(eval(input()))
        except EOFError:
            break

MAX = 50000
primes = list()
for i in range(MAX):
    primes.append(True)
primes[0] = False
primes[1] = False

for i in range(2, MAX):
    j = i + i
    while j < MAX:
        primes[j] = False
        j = j + i

while True:
    N = int(eval(input()))
    if N == 0:
        break
    ans = 0
    for i in range(1,N//2 + 1):
        if primes[i] and primes[N-i]:
            ans += 1
    print(ans)



# Optimized solution
def get_input():
    while True:
        try:
            yield ''.join(eval(input()))
        except EOFError:
            break

MAX = 50000
primes = list()
for i in range(MAX):
    primes.append(True)
primes[0] = False
primes[1] = False

for i in range(2, MAX):
    j = i + i
    while j < MAX:
        primes[j] = False
        j = j + i

while True:
    N = int(eval(input()))
    if N == 0:
        break
    ans = 0
    if N % 2 == 0:
        for i in range(1,N//2 + 1):
            if primes[i] and primes[N-i]:
                ans += 1
    else:
        if primes[2] and primes[N-2]:
            ans += 1
    print(ans)
# Original solution
n=50000
p=[1]*(n+1)
p[0],p[1]=0,0
for i in range(2,int(n**0.5)+1):
    if p[i]:        
        for j in range(i*i,n+1,i):
            p[j]=0
#p=[i for i in range(n+1) if p[i]==1]
while 1:
    n=int(eval(input()))
    if n==0:break
    c=0
    for i in range(2,n//2+1):
        if(p[i],p[n-i])==(1,1):c+=1
    print(c)

# Optimized solution
p=[1]*50001
for i in range(2,int(50000**0.5)+1):
    if p[i]:
        for j in range(i*i,50000,i):p[j]=0
while 1:
    n=int(eval(input()))
    if n==0:break
    print((sum(1 for i in range(2,n//2+1) if p[i] and p[n-i])))
# Original solution
import bisect,sys
from itertools import *
n=list(range(50001));a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in sys.stdin:
 x=int(x)
 if x:print((sum(1 for d in p[:bisect.bisect(p,x//2)]if a[x-d])))


# Optimized solution
import bisect,sys
from itertools import *
n=list(range(50001));a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in map(int,sys.stdin):
 if x:print((len([1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]])))
# Original solution
from bisect import bisect_left
ub = 50000
primes = {2} | set(range(3, ub, 2))
du = primes.difference_update
for n in range(3, ub, 2):
    if n in primes:
        du(list(range(n*3, ub, n*2)))

primes = list(primes)

while True:
    n = int(eval(input()))
    if n == 0:
        break
    l, r = 0, bisect_left(primes, n-2)
    ans = 0
    while l <= r:
        if primes[l]+primes[r] > n:
            r -= 1
        ans += (primes[l]+primes[r] == n)
        l += 1
    print(ans)


# Optimized solution
import sys
from bisect import bisect_right
from itertools import chain, compress

ub = 50000
is_prime = [0, 0, 1, 1] + [0]*(ub-3)
is_prime[5::6] = is_prime[7::6] = [1]*int(ub/6)
primes = [2, 3]
append = primes.append

for n in chain(list(range(5, ub, 6)), list(range(7, ub, 6))):
    if is_prime[n]:
        append(n)
        is_prime[n*3::n*2] = [0]*((ub-n)//(n*2))
primes.sort()

for n in map(int, sys.stdin):
    if not n:
        break
    if n%2:
        print((is_prime[n-2]))
    else:
        print((len([1 for p in primes[:bisect_right(primes, n/2)] if is_prime[n-p]])))