Problem: A set of four prime numbers arranged like (a, a + 2, a + 6, a + 8) is called a quadruplet prime number. Of the four prime numbers that make up a quadruplet prime, the largest number is called the size of the quadruplet prime. For example, the smallest prime quadruplet is a set of (5, 7, 11, 13), which is 13 in size. The next largest prime quadruplet is the set of (11, 13, 17, 19), which is 19 in size.

Create a program that takes the integer n (13 ≤ n ≤ 10,000,000) as input and outputs the maximum size of the quadruplet prime numbers whose size is n or less.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. One integer n is given on one row for each dataset.

The number of datasets does not exceed 2000.

Output

Outputs the maximum prime quadruplet size on one line for each input dataset.

Example

Input

13
14
15
16
17
18
19
20
10000
0


Output

13
13
13
13
13
13
19
19
9439

Solution (in JAVA):

Solution:
import java.util.*;


public class Main {
	
	void AOJ0222(){
		int MAX=10000001;
		boolean[] list = new boolean[MAX+1];
		Arrays.fill(list, true);
		list[1]=false;
		for(int i=2; i<=MAX; i++) {
			if(list[i]) {
				for (int j=i+i; j<+MAX; j+=i)	list[j] = false;
			}
		}
		
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(n==0)	break;
			for(int i=n; i>6; i--){
				if(list[i] && list[i-2] && list[i-6] && list[i-8]){
					System.out.println(i);
					break;
				}
				//debug
				//System.out.println(i);
			}
			//System.out.println(-1);
		}
	}
	
	void AOJ0185(){
		int MAX=1000001;
		boolean[] list = new boolean[MAX+1];
		Arrays.fill(list, true);
		list[1]=false;
		for(int i=2; i<=MAX; i++) {
			if(list[i]) {
				for (int j=i+i; j<+MAX; j+=i)	list[j] = false;
			}
		}
		
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(n==0)	break;
			int count=0;
			for(int i=1; i<=n/2; i++){
				if(list[i] && list[n-i]){
					count++;
				}
			}
			System.out.println(count);
		}
	}
	
	void AOJ0056(){
		int MAX=100000;
		boolean[] list = new boolean[MAX+1];
		Arrays.fill(list, true);
		list[1]=false;
		for(int i=2; i<=MAX; i++) {
			if(list[i]) {
				for (int j=i+i; j<+MAX; j+=i)	list[j] = false;
			}
		}
		
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(n==0)	break;
			int count=0;
			for(int i=1; i<=n/2; i++){
				//System.out.println("I"+i+" N-I"+(n-i));
				if(list[i] && list[n-i]){
					//System.out.println("I"+i+" N-I"+(n-i));
					count++;
				}
			}
			System.out.println(count);
		}
	}
	
	void Old2AOJ0056(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(n==0)	break;
			int count=0;
			for(int i=1; i<=n/2; i++){
				if(isPrime(i)&&isPrime(n-i))	count++;
			}
			System.out.println(count);
		}
	}
	
	void OldAOJ0056(){
		
		int MAX=100000;
		boolean[] list = new boolean[MAX+1];
		Arrays.fill(list, true);
		int[] prime = new int[MAX];
		int c=0;
		for(int i=2; i<=MAX; i++) {
			if(list[i]) {
				prime[c]=i;
				c++;
				for (int j=i+i; j<+MAX; j+=i)	list[j] = false;
			}
		}
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(n==0)	break;
			int count=0;
			for(int i=0; i<n; i++){
				if(prime[i]>n)	break;
				for(int j=i; j<n; j++){
					int sum = prime[i]+prime[j];
					if(sum > n)	break;
					if(sum == n)	count++;
				}
			}
			System.out.println(count);
		}
	}
	
	void AOJ0150(){
		int MAX=10000;
		boolean[] list = new boolean[MAX+1];
		Arrays.fill(list, true);
		boolean[] flag = new boolean[MAX+1];
		Arrays.fill(flag, false);
		int last = -1;
		for(int i=2; i<=MAX; i++){
			if(list[i]){
				if(i-last == 2)	flag[i]=true;
				last=i;
				for(int j=i+i; j<=MAX; j+=i)	list[j]=false;
			}
		}
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(n==0)	break;
			for(int i=n; i>0; i--){
				if(flag[i]){
					System.out.println(i-2+" "+i);
					break;
				}
			}
			//debug
			//System.out.println(-1);
		}
	}
	
	void AOJ0053(){
		int MAX = 10000000;
		boolean[] list = new boolean[MAX+1];
		Arrays.fill(list, true);
		int count=1;
		long[] sum = new long[10001];
		sum[0]=0;
		for(int i=2; i<=MAX; i++){
			if(list[i]){
				sum[count] = sum[count-1]+(long)i;
				count++;
				for(int j=i+i; j<=MAX; j+=i)	list[j]=false;
			}
			if(count>10000) break;
		}
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(n==0)	System.exit(0);
			System.out.println(sum[n]);
		}
	}
	
	void AOJ0044(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			for(int i=n-1; i>1; i--){
				if(isPrime(i)){
					System.out.print(i+" ");
					break;
				}
			}
			for(int i=n+1; ; i++){
				if(isPrime(i)){
					System.out.println(i);
					break;
				}
			}
		}
	}
	
	void AOJ0009(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int count=0;
			boolean[] prime = new boolean[n+1];
			Arrays.fill(prime, true);
			for(int i=2; i<=n; i++){
				if(prime[i]){
					count++;
					for(int j=i+i; j<=n; j+=i)	prime[j]=false;
				}
			}
			System.out.println(count);
		}
	}
	
	
	ArrayList<Integer> Sieve(int n){
	     ArrayList<Integer> prime = new ArrayList<Integer>();
	     if(n<2)	return prime;
	     boolean[] list = new boolean[n];
	     Arrays.fill(list, true);
	     list[1]=false;
	     for (int i=2; i<n; i++) {
	          if (list[i]) {
	               prime.add(i);
	               for (int j=i+i; j<n; j+=i)	list[j] = false;
	          }
	     }
	     return prime;
	}
	
	boolean[] Sieve2(int MAX){
		boolean[] list = new boolean[MAX+1];
		Arrays.fill(list, true);
		list[1]=false;
		for(int i=2; i<=MAX; i++) {
			if(list[i]) {
				for (int j=i+i; j<+MAX; j+=i)	list[j] = false;
			}
		}
		return list;
	}

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

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

}