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.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc;

	static final int INF=1<<28;
	static final double EPS=1e-9;

	void run(){
		sc=new Scanner(System.in);

		boolean[] isPrimes=new boolean[50000];
		for(int i=2; i<isPrimes.length; i++)
			isPrimes[i]=isPrime(i);

		for(;;){
			int n=sc.nextInt();
			if(n==0)
				break;
			int ans=0;
			if(n%2==1){
				ans=isPrimes[n-2]?1:0;
			}else{
				for(int i=2; 2*i<=n; i++)
					if(isPrimes[i]&&isPrimes[n-i])
						ans++;
			}
			println(ans+"");
		}
		sc.close();
	}

	boolean isPrime(int n){
		int m=(int)sqrt(n);
		for(int i=2; i<=m; i++)
			if(n%i==0)
				return false;
		return true;
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}