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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] primeList = new int[5134];//5134
        int limit = 50001;
        primeList[0] = 2;
        primeList[1] = 3;
        int count = 2;
        for (int i = 5; i < limit; i += 2) {
            boolean wflag = true;
            for (int j = 1; primeList[j] * primeList[j] <= i; j++) {
                if (i % primeList[j] == 0) {
                    wflag = false;
                    break;
                }
            }
            if (wflag) {
                primeList[count++] = i;
            }
        }
        int[] l = new int[limit];
        for (int i = 0; primeList[i]>0; i++) {
            for (int j = i; primeList[j]>0; j++) {
                int s = primeList[i] + primeList[j];
                if (s < limit) {
                    l[s]++;
                }
            }
        }
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            System.out.println(l[n]);
        }

    }
}

