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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));
		StringBuilder builder = new StringBuilder();
		int max = 50000;
		boolean[] primes = new boolean[max + 1];
		int count = 1;
		for (int i = 3; i <= max; i += 2) {
			if (!primes[i]) {
				count++;
				if (i <= Math.sqrt(max)) {
					for (int j = i; j <= max / i; j += 2) {
						primes[(int) (i * j)] = true;
					}
				}
			}
		}
		int[] prime = new int[count];
		prime[0] = 2;
		int count2 = 1;
		for (int i = 3; i <= max; i += 2) {
			if (!primes[i]) {
				prime[count2] = i;
				count2++;
			}
		}
		int[] g = new int[max + 1];
		for (int i = 0; i <= prime.length; i++) {
			for (int j = i; j < prime.length && prime[i] + prime[j] <= max; j++) {
				g[prime[i] + prime[j]]++;
			}
		}

		while (true) {
			int n = Integer.parseInt(reader.readLine());
			if (n == 0) {
				break;
			}
			builder.append(g[n]).append('\n');
		}
		System.out.print(builder);

	}
}