#include <bits/stdc++.h>
using namespace std;
inline long long isqrt(long long n){
long double N = n;
N = sqrtl(N);
long long sq = N - 2;
sq = max(sq, 0LL);
while(sq * sq < n){
sq++;
}
if((sq * sq) == n) return sq;
return sq - 1;
}
set<long long> a;
int maxSize = 10000;
int main(){
for (int i = 1; i <= 20; i++) {
a.insert(i);
}
while (a.size() <= maxSize) {
set<long long> s = a;
for (auto x : a) {
for (auto y : a) {
s.insert(x * x + y * y);
}
}
for (auto x : a) {
for (auto y : a) {
for (auto z : a) {
int d2 = x * x + y * y - z * z;
int d = isqrt(d2);
if (d2 == d * d && d > 0) {
s.insert(d);
}
}
}
}
a = s;
}
int i = 1;
for (auto x : a) {
if (x != i) {
cout << "The first integer that is not in S is " << x << endl;
break;
}
++i;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbmxpbmUgbG9uZyBsb25nIGlzcXJ0KGxvbmcgbG9uZyBuKXsKICAgIGxvbmcgZG91YmxlIE4gPSBuOwogICAgTiA9IHNxcnRsKE4pOwogICAgbG9uZyBsb25nIHNxID0gTiAtIDI7CiAgICBzcSA9IG1heChzcSwgMExMKTsKICAgIHdoaWxlKHNxICogc3EgPCBuKXsKICAgICAgICBzcSsrOwogICAgfQogICAgaWYoKHNxICogc3EpID09IG4pIHJldHVybiBzcTsKICAgIHJldHVybiBzcSAtIDE7Cn0KCnNldDxsb25nIGxvbmc+IGE7CmludCBtYXhTaXplID0gMTAwMDA7CgppbnQgbWFpbigpewogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gMjA7IGkrKykgewogICAgICAgIGEuaW5zZXJ0KGkpOwogICAgfQogICAgd2hpbGUgKGEuc2l6ZSgpIDw9IG1heFNpemUpIHsKICAgICAgICBzZXQ8bG9uZyBsb25nPiBzID0gYTsKICAgICAgICBmb3IgKGF1dG8geCA6IGEpIHsKICAgICAgICAgICAgZm9yIChhdXRvIHkgOiBhKSB7CiAgICAgICAgICAgICAgICBzLmluc2VydCh4ICogeCArIHkgKiB5KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBmb3IgKGF1dG8geCA6IGEpIHsKICAgICAgICAgICAgZm9yIChhdXRvIHkgOiBhKSB7CiAgICAgICAgICAgICAgICBmb3IgKGF1dG8geiA6IGEpIHsKICAgICAgICAgICAgICAgICAgICBpbnQgZDIgPSB4ICogeCArIHkgKiB5IC0geiAqIHo7CiAgICAgICAgICAgICAgICAgICAgaW50IGQgPSBpc3FydChkMik7CiAgICAgICAgICAgICAgICAgICAgaWYgKGQyID09IGQgKiBkICYmIGQgPiAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIHMuaW5zZXJ0KGQpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBhID0gczsKICAgIH0KICAgIGludCBpID0gMTsKICAgIGZvciAoYXV0byB4IDogYSkgewogICAgICAgIGlmICh4ICE9IGkpIHsKICAgICAgICAgICAgY291dCA8PCAiVGhlIGZpcnN0IGludGVnZXIgdGhhdCBpcyBub3QgaW4gUyBpcyAiIDw8IHggPDwgZW5kbDsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICAgICsraTsKICAgIH0KICAgIHJldHVybiAwOwp9