#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define trav(i, a) for(auto& i: a)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define si(a) ((int)(a).size())
#define ins insert
#define pb push_back
#define mp make_pair
#define f first
#define s second
const int MOD = 1e9 + 7;
const int INF = 1e18;
const string nl = "\n";
struct timer {
decltype(chrono::high_resolution_clock::now()) begin;
void start() {
begin = chrono::high_resolution_clock::now();
}
void end() {
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end - begin).count();
cerr << duration << "ms elapsed" << endl;
}
};
const int N = 1e8;
vector<bool> isp(N, true);
void sieve() {
isp[0] = isp[1] = 0;
for(int i = 2; i < N; ++i) {
if(!isp[i]) {
continue;
}
for(int j = i * i; j < N; j += i) {
isp[j] = false;
}
}
}
vector<bool> is_prime(N, true);
void sieve1() {
is_prime[0] = is_prime[1] = 0;
for(int i = 2; i < N; ++i) {
for(int j = i * i; j < N; j += i) {
is_prime[j] = false;
}
}
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
timer a;
a.start();
sieve();
a.end();
a.start();
sieve1();
a.end();
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGludCBpbnQ2NF90CiNkZWZpbmUgdHJhdihpLCBhKSBmb3IoYXV0byYgaTogYSkKI2RlZmluZSBhbGwoYSkgYS5iZWdpbigpLCBhLmVuZCgpCiNkZWZpbmUgcmFsbChhKSBhLnJiZWdpbigpLCBhLnJlbmQoKQojZGVmaW5lIHNpKGEpICgoaW50KShhKS5zaXplKCkpCiNkZWZpbmUgaW5zIGluc2VydAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGYgZmlyc3QKI2RlZmluZSBzIHNlY29uZAoKY29uc3QgaW50IE1PRCA9IDFlOSArIDc7CmNvbnN0IGludCBJTkYgPSAxZTE4Owpjb25zdCBzdHJpbmcgbmwgPSAiXG4iOwoKc3RydWN0IHRpbWVyIHsKCWRlY2x0eXBlKGNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKSkgYmVnaW47Cgl2b2lkIHN0YXJ0KCkgewoJCWJlZ2luID0gY2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpOwoJfQoJdm9pZCBlbmQoKSB7CgkJYXV0byBlbmQgPSBjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CgkJYXV0byBkdXJhdGlvbiA9IGNocm9ubzo6ZHVyYXRpb25fY2FzdDxjaHJvbm86Om1pbGxpc2Vjb25kcz4oZW5kIC0gYmVnaW4pLmNvdW50KCk7CgkJY2VyciA8PCBkdXJhdGlvbiA8PCAibXMgZWxhcHNlZCIgPDwgZW5kbDsKCX0KfTsKCmNvbnN0IGludCBOID0gMWU4OwoKdmVjdG9yPGJvb2w+IGlzcChOLCB0cnVlKTsKCnZvaWQgc2lldmUoKSB7Cglpc3BbMF0gPSBpc3BbMV0gPSAwOwoJZm9yKGludCBpID0gMjsgaSA8IE47ICsraSkgewoJCWlmKCFpc3BbaV0pIHsKCQkJY29udGludWU7CgkJfQoJCWZvcihpbnQgaiA9IGkgKiBpOyBqIDwgTjsgaiArPSBpKSB7CgkJCWlzcFtqXSA9IGZhbHNlOwoJCX0KCX0KfQoKdmVjdG9yPGJvb2w+IGlzX3ByaW1lKE4sIHRydWUpOwoKdm9pZCBzaWV2ZTEoKSB7Cglpc19wcmltZVswXSA9IGlzX3ByaW1lWzFdID0gMDsKCWZvcihpbnQgaSA9IDI7IGkgPCBOOyArK2kpIHsKCQlmb3IoaW50IGogPSBpICogaTsgaiA8IE47IGogKz0gaSkgewoJCQlpc19wcmltZVtqXSA9IGZhbHNlOwoJCX0KCX0KfQoKaW50MzJfdCBtYWluKCkgewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKG51bGxwdHIpOwoKCXRpbWVyIGE7CglhLnN0YXJ0KCk7CglzaWV2ZSgpOwoJYS5lbmQoKTsKCWEuc3RhcnQoKTsKCXNpZXZlMSgpOwoJYS5lbmQoKTsKfQo=