#include <bits/stdc++.h> #define int long long using namespace std; int ksm(int a,int b,int p) { int res = 1,t = a; while (b) { if (b & 1) res = (res * t) % p; t = (t * t) % p; b >>= 1; } return res; } signed main() { int n; while (true) { cin >> n; if (!n) break; printf("%lld\n",(ksm(2,n - 1,n) + 1) % n); } return 0; }