#include <stdlib.h>
static void precalc(unsigned div, unsigned *mulp, int *prep, int *postp, int *incp)
{
  int bits = 0;
again:
  *prep = bits;
  unsigned pow = 1u<<31, quo = pow / div, rem = pow % div;

  int log=0, exp;
  unsigned tmp=div;
  do log++; while (tmp >>= 1);

  unsigned down_mul=0;
  for (exp=0, pow=1u<<bits; ; exp++, pow<<=1) {
    int adj = rem >= div - rem;
    quo *= 2; rem *= 2;
    if (adj) {quo++; rem -= div; }

    if (exp >= log-bits || div-rem <= pow)
      break;

    if (!down_mul && rem <= pow) {
      down_mul = quo; *postp = exp;
    }
  }
  if (exp < log) {
    *mulp = quo+1;
    *postp = exp;
    *incp = 0;
  } else if (div & 1) {
    *mulp = down_mul;
    *incp = 1;
  } else {
    do bits++; while (!((div >>= 1) & 1));
    goto again;
  }
}
int main(int argc, char *argv[])
{
  unsigned div = atoi(argv[1]);
  if (!(div&(div-1)))
    return 0;

  unsigned mul;
  int pre, post, inc;
  precalc(div, &mul, &pre, &post, &inc);
  unsigned s32 = 32;
  if (sizeof(long) == 8) {
    s32 += post;
    post = 0;
  }
  unsigned rem, quo, val;
  char bad=0;
#define loop(pre, inc, post) ({    \
  for (val=~0u, quo=val/div, rem=val%div+1; quo+1; quo--, rem=div)      \
    for (; rem; rem--, val--) {  \
      unsigned v = val;            \
      v >>= pre;                   \
      if (v+inc) v+=inc;           \
      v = (1ull * v * mul) >> s32; \
      v >>= post;                  \
      bad |= (v != quo);      \
    } })
  if (post)
    if (inc)
      if (pre)
        return 2;
      else
        loop(0, inc, post);
    else
      if (pre)
        loop(pre, 0, post);
      else
        loop(0, 0, post);
  else
    if (inc)
      if (pre)
        return 2;
      else
        loop(0, inc, 0);
    else
      if (pre)
        loop(pre, 0, 0);
      else
        loop(0, 0, 0);
  return bad;
}