#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;
}