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 -*-

import sys

def make_prime_list(lim):
    lst = [True for i in xrange(lim + 1)]

    num = 2
    while num ** 2 <= lim:
        for i in xrange(num * 2, lim + 1, num):
            lst[i] = False
        num += 1
        while not lst[num]:
            num += 1
    return [i for i in xrange(2, lim + 1) if lst[i]]

def binary_search(n, prime_list):
    rLim = len(prime_list) - 1
    lLim = 0
    while lLim < rLim:
        middle = (rLim + lLim) / 2
        if prime_list[middle] == n:
            return middle
        elif prime_list[middle] < n:
            lLim = middle + 1
        else:
            rLim = middle - 1
    while prime_list[rLim] < n and rLim < len(prime_list) - 1:
        rLim += 1
    return rLim    

def solve():
    prime_list = make_prime_list(50000)
    while True:
        n = input()
        if n > 0:
            if n % 2 == 0:
                count = 0
                index = 0
                rev_index = binary_search(n, prime_list)
                while index <= rev_index:
                    while prime_list[index] + prime_list[rev_index] > n:
                        rev_index -= 1
                    if index <= rev_index and prime_list[index] + prime_list[rev_index] == n:
                        count += 1
                    index += 1
                print count
            else:
                if n - 2 in prime_list:
                    print 1
                else:
                    print 0
        else:
            sys.exit()

if __name__ == "__main__":
    solve()    