Two best friends Serozha and Gena play a game.

Initially there is one pile consisting of n stones on the table. During one move one pile should be taken and divided into an arbitrary number of piles consisting of a1 > a2 > ... > ak > 0 stones. The piles should meet the condition a1 - a2 = a2 - a3 = ... = ak - 1 - ak = 1. Naturally, the number of piles k should be no less than two.

The friends play in turns. The player who cannot make a move loses. Serozha makes the first move. Who will win if both players play in the optimal way?

Input

The single line contains a single integer n (1 ≤ n ≤ 105).

Output

If Serozha wins, print k, which represents the minimal number of piles into which he can split the initial one during the first move in order to win the game.

If Gena wins, print "-1" (without the quotes).

Examples

Input

3


Output

2


Input

6


Output

-1


Input

100


Output

8
#include <bits/stdc++.h>
using namespace std;
int nimber[100000 + 1];
int min_piles[100000 + 1];
char pv[1000];
int primesize;
vector<int> prime;
int expindex;
int pfactor[20];
int exponent[20];
void Build_Primetable(int limit);
int get_factorNumber(int number);
int main(int argc, char* argv[]) {
  int input = 0;
  cin >> input;
  Build_Primetable(100000);
  int i, j, k;
  int sum = 0;
  int start, end;
  nimber[1] = 0;
  nimber[2] = 0;
  for (int n = 3; n <= 100000; n++) {
    int factor_number;
    int factor;
    int power[20] = {0};
    int a, b, larger, smaller;
    int number = n * 8;
    factor_number = get_factorNumber(number);
    int max = 0;
    for (i = 0; i < 1000; i++) {
      pv[i] = 0;
    }
    for (i = 0; i < factor_number / 2; i++) {
      factor = 1;
      if (i > 0) {
        power[0]++;
      }
      j = 0;
      while (power[j] > exponent[j]) {
        power[j + 1]++;
        power[j] = 0;
        j++;
      }
      if (j > max) {
        max = j;
      }
      for (j = 0; j <= max; j++) {
        for (k = 0; k < power[j]; k++) {
          factor *= pfactor[j];
        }
      }
      a = factor;
      b = number / factor;
      if ((a & 1) == 0 && (b & 1) == 0) {
        int sqroot = (a + b) >> 1;
        larger = (a > b) ? a : b;
        smaller = (a < b) ? a : b;
        int piles = smaller >> 1;
        int x = larger + 1 - sqroot;
        if ((x & 1) == 0 && piles > 1) {
          start = x >> 1;
          end = start + piles;
          int v = 0;
          for (k = start; k < end; k++) {
            v ^= nimber[k];
          }
          pv[v] = 1;
          if (!v) {
            if (min_piles[n] == 0) min_piles[n] = piles;
            if (piles < min_piles[n]) min_piles[n] = piles;
          }
        }
      }
    }
    for (i = 0; i <= 100000; i++) {
      if (!pv[i]) {
        nimber[n] = i;
        break;
      }
    }
  }
  int ans = (nimber[input]) ? min_piles[input] : -1;
  cout << ans;
  return 0;
}
void Build_Primetable(int limit) {
  int midpoint;
  bool got_it;
  prime.push_back(2);
  midpoint = (int)sqrt(limit);
  for (int i = 3; i <= midpoint; i = i + 2) {
    got_it = true;
    int square;
    for (int j = 1; j < prime.size(); j++) {
      square = prime[j];
      square *= square;
      if (square > i) break;
      if (i % prime[j] == 0) {
        got_it = false;
        break;
      }
    }
    if (got_it == true) {
      prime.push_back(i);
    }
  }
  int newstart = midpoint;
  bool bFindNextPrimeNumber = false;
  while (!bFindNextPrimeNumber) {
    got_it = true;
    for (int j = 0; j < primesize; j++) {
      if (newstart % prime[j] == 0) {
        got_it = false;
        break;
      }
    }
    if (got_it) {
      prime.push_back(newstart);
      bFindNextPrimeNumber = true;
    }
    newstart++;
  }
  primesize = prime.size();
}
int get_factorNumber(int number) {
  expindex = 0;
  for (int i = 0; i < primesize; i++) {
    exponent[expindex] = 0;
    bool isPrimeFactor = false;
    if (number == 1) {
      break;
    }
    int n = prime[i];
    if (n * n > number) {
      pfactor[expindex] = number;
      exponent[expindex]++;
      expindex++;
      break;
    }
    while (number % prime[i] == 0) {
      number /= prime[i];
      pfactor[expindex] = prime[i];
      exponent[expindex]++;
      isPrimeFactor = true;
    }
    if (isPrimeFactor) {
      expindex++;
    }
  }
  int fNumber = 1;
  for (int i = 0; i < expindex; i++) {
    fNumber *= (exponent[i] + 1);
  }
  return fNumber;
}
