It is known that even numbers greater than or equal to 4 can be represented by the sum of two prime numbers. This is called the Goldbach's conjecture, and computer calculations have confirmed that it is correct up to a fairly large number. For example, 10 can be represented by the sum of two prime numbers, 7 + 3 and 5 + 5.

Write a program that inputs the integer n and outputs how many combinations of n are the sum of two prime numbers. However, n must be 4 or more and 50,000 or less. Also, the n entered is not always even.



Input

Given multiple datasets. Each dataset is given n on one row. When n is 0, it is the last input. The number of datasets does not exceed 10,000.

Output

For each dataset, output the number of combinations in which n is the sum of two prime numbers on one line.

Example

Input

10
11
0


Output

2
0
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def enum_prime(m):
    L = [True for _ in xrange(m + 1)]
    L[0] = L[1] = False

    for i in xrange(2, m + 1):
        if L[i]:
            for j in xrange(i + i, m + 1, i):
                L[j] = False
            if m < i * i:
                break
    return L

FLAGS = enum_prime(50000)
PRIMES = [i for i, isprime in enumerate(FLAGS) if isprime]

for line in stdin:
    if line.startswith('0'):
        break
    n = int(line)
    n2 = n // 2
    cnt = 0
    if n % 2 == 0:
        for p in PRIMES:
            if p > n2:
                break
            if FLAGS[n - p]:
                cnt += 1
    elif FLAGS[n - 2]:
        cnt = 1
    print(cnt)