#include<bits/stdc++.h>
using namespace std;
#define SIZE 2000
#define ll long long
#define MOD 1000003ll
ll phi(ll n)
{
float result = n;
ll num = n;
for (ll p = 2; p * p <= n; ++p)
{
if (n % p == 0)
{
while (n % p == 0)
n /= p;
result *= (1.0 - (1.0 / (float) p));
}
}
if (n > 1)
result *= (1.0 - (1.0 / (float) n));
ll ans = ((ll)result * num / 2);
ans = num * (num + 1) / 2 - ans;
return ans % MOD;
}
ll phifunc(ll n)
{
if (n <= 2) return n;
ll temp = n;
ll ans = n;
for (ll i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
ans -= ans / i;
while (n % i == 0)
n /= i;
}
}
if (n > 1)
ans -= ans / n;
ans = (ans / 2 * temp);
ans = (temp * (temp + 1) / 2) - ans;
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
for (int i = 2; i < SIZE; i++)
{
if (phi(i) != phifunc(i))
cout << i << endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBTSVpFIDIwMDAKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBNT0QgMTAwMDAwM2xsCgpsbCBwaGkobGwgbikKewoJZmxvYXQgcmVzdWx0ID0gbjsKCWxsIG51bSA9IG47CgoJZm9yIChsbCBwID0gMjsgcCAqIHAgPD0gbjsgKytwKQoJewoKCQlpZiAobiAlIHAgPT0gMCkKCQl7CgoJCQl3aGlsZSAobiAlIHAgPT0gMCkKCQkJCW4gLz0gcDsKCQkJcmVzdWx0ICo9ICgxLjAgLSAoMS4wIC8gKGZsb2F0KSBwKSk7CgkJfQoJfQoKCglpZiAobiA+IDEpCgkJcmVzdWx0ICo9ICgxLjAgLSAoMS4wIC8gKGZsb2F0KSBuKSk7CgoJbGwgYW5zID0gKChsbClyZXN1bHQgKiBudW0gLyAyKTsKCWFucyA9IG51bSAqIChudW0gKyAxKSAvIDIgLSBhbnM7CgoJcmV0dXJuIGFucyAlIE1PRDsKfQoKbGwgcGhpZnVuYyhsbCBuKQp7CgoJaWYgKG4gPD0gMikgcmV0dXJuIG47CgoJbGwgdGVtcCA9IG47CgoJbGwgYW5zID0gbjsKCglmb3IgKGxsIGkgPSAyOyBpICogaSA8PSBuOyBpKyspCgl7CgkJaWYgKG4gJSBpID09IDApCgkJewoJCQlhbnMgLT0gYW5zIC8gaTsKCQkJd2hpbGUgKG4gJSBpID09IDApCgkJCQluIC89IGk7CgkJfQoJfQoKCWlmIChuID4gMSkKCQlhbnMgLT0gYW5zIC8gbjsKCglhbnMgPSAoYW5zIC8gMiAqIHRlbXApOwoJYW5zID0gKHRlbXAgKiAodGVtcCArIDEpIC8gMikgLSBhbnM7CgoJcmV0dXJuIGFuczsKCn0KCmludCBtYWluKCkKewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKDApOyBjb3V0LnRpZSgwKTsKI2lmbmRlZiBPTkxJTkVfSlVER0UKCWZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwoJZnJlb3Blbigib3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKI2VuZGlmCgoJZm9yIChpbnQgaSA9IDI7IGkgPCBTSVpFOyBpKyspCgl7CgkJaWYgKHBoaShpKSAhPSBwaGlmdW5jKGkpKQoJCQljb3V0IDw8IGkgPDwgZW5kbDsKCX0KCgoJcmV0dXJuIDA7Cn0=