import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
// 100万までの素数素数を求める
long t
= System.
currentTimeMillis();
boolean[] p = new boolean[1000000];
for(int i = 3; i < 1000; i += 2){
for(int j = i*i; j < 1000000; j += i+i) p[j] = true;
}
int[] prime = new int[80000];
prime[0] = 2;
int n = 0;
for(int i = 3; i < 1000000; i += 2){
if(!p[i]) prime[++n] = i;
}
t
= System.
currentTimeMillis() - t
; }
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CiAKLyogTmFtZSBvZiB0aGUgY2xhc3MgaGFzIHRvIGJlICJNYWluIiBvbmx5IGlmIHRoZSBjbGFzcyBpcyBwdWJsaWMuICovCmNsYXNzIElkZW9uZQp7CgkvLyAxMDDkuIfjgb7jgafjga7ntKDmlbDntKDmlbDjgpLmsYLjgoHjgosKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbiB7CgkJbG9uZyB0ID0gIFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwogCgkJYm9vbGVhbltdIHAgPSBuZXcgYm9vbGVhblsxMDAwMDAwXTsKCQlmb3IoaW50IGkgPSAzOyBpIDwgMTAwMDsgaSArPSAyKXsKCQkJZm9yKGludCBqID0gaSppOyBqIDwgMTAwMDAwMDsgaiArPSBpK2kpIHBbal0gPSB0cnVlOwoJCX0KIAoJCWludFtdIHByaW1lID0gbmV3IGludFs4MDAwMF07CgkJcHJpbWVbMF0gPSAyOwoJCWludCBuID0gMDsKCQlmb3IoaW50IGkgPSAzOyBpIDwgMTAwMDAwMDsgaSArPSAyKXsKCQkJaWYoIXBbaV0pIHByaW1lWysrbl0gPSBpOwoJCX0KIAoJCXQgPSBTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMoKSAtIHQ7CgkJU3lzdGVtLm91dC5wcmludGxuKHQgKyAibXMiKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4obik7Cgl9Cn0=