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;
static const int bitindex_map[32] = {};
const int dir[][2] = {{-1, 0}, {0, 1},  {1, 0},  {0, -1},
                      {1, 1},  {1, -1}, {-1, 1}, {-1, -1}};
const char dname[] = "NWSE";
template <typename T>
inline void updateMax(T& a, const T& b) {
  a = max(a, b);
}
template <typename T>
inline void updateMin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
inline vector<T> erase(vector<T> table, int ind) {
  assert(ind < table.size());
  table.erase(table.begin() + ind);
  return table;
}
template <typename T>
vector<T> unique(vector<T> table) {
  sort(table.begin(), table.end());
  vector<T> res;
  unique_copy(table.begin(), table.end(), back_inserter(res));
  return res;
}
template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& pp) {
  out << "(" << pp.first << "," << pp.second << ")";
  return out;
}
template <typename A, typename B>
istream& operator<<(istream& in, pair<A, B>& pp) {
  cerr << "A pair wanted" << endl;
  in >> pp.first >> pp.second;
  return in;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& vect) {
  copy(vect.begin(), vect.end(), ostream_iterator<T>(out, " "));
  return out;
  out << "length = " << vect.size() << endl;
  for (int i = 0; i < vect.size(); i++) out << vect[i] << " ";
  out << endl;
  return out;
}
ostream& operator<<(ostream& out, const vector<string>& vect) {
  out << vect.size() << " X " << vect[0].length() << endl;
  for (int i = 0; i < vect.size(); i++) out << vect[i] << endl;
  return out;
}
template <typename T>
istream& operator>>(istream& in, vector<T>& vect) {
  vect.clear();
  int n;
  cerr << "A integer of length wanted" << endl;
  in >> n;
  vect.resize(n);
  cerr << n << " elements wanted" << endl;
  for (int i = 0; i < n; i++) in >> vect[i];
  return in;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<vector<T> >& vect) {
  out << "row number=" << vect.size() << endl;
  for (int i = 0; i < vect.size(); i++) {
    out << "row #" << i << ":";
    for (int j = 0; j < vect[i].size(); j++) out << " " << vect[i][j];
    out << endl;
  }
  return out;
}
template <typename T>
istream& operator>>(istream& in, vector<vector<T> >& vect) {
  vect.clear();
  int n, m;
  cerr << "Two integers wanted" << endl;
  in >> n >> m;
  vect.resize(n);
  cerr << "A matrix " << n << " X " << m << " wanted" << endl;
  for (int i = 0; i < n; i++) {
    vect[i].resize(m);
    for (int j = 0; j < m; j++) in >> vect[i][j];
  }
  return in;
}
template <class T>
string convert(T vv) {
  ostringstream re;
  re << vv;
  return re.str();
}
template <typename T>
T convert(const string& ss) {
  istringstream is(ss);
  T tmp;
  is >> tmp;
  return tmp;
}
template <class T>
string convert(vector<T> vv) {
  ostringstream re;
  for (int i = 0; i < vv.size(); i++) {
    if (i) re << " ";
    re << vv[i];
  }
  return re.str();
}
template <class T>
vector<T> parse(const string& ss, const char* cut = " ") {
  vector<T> re;
  for (int j = 0; j < ss.size(); j++) {
    string s;
    while (j < ss.size() && NULL == strchr(cut, ss[j])) s += ss[j++];
    if (!s.empty()) {
      T tmp;
      istringstream is(s);
      is >> tmp;
      re.push_back(tmp);
    }
  }
  return re;
}
template <>
vector<string> parse(const string& ss, const char* cut) {
  vector<string> re;
  for (int j = 0; j < ss.size(); j++) {
    string s;
    while (j < ss.size() && NULL == strchr(cut, ss[j])) s += ss[j++];
    if (!s.empty()) {
      re.push_back(s);
    }
  }
  return re;
}
int countBit(int n) {
  return __builtin_popcount(n);
  int re = 0;
  while (n) re++, n ^= ((((n) ^ ((n)-1)) & n));
  return re;
}
int MSB(int n) {
  if (n == 0) return 0;
  while (((((n) ^ ((n)-1)) & n)) != n) n ^= ((((n) ^ ((n)-1)) & n));
  return n;
}
void initHash(int n, int hash[]) {
  for (int i = 0; i < n; i++) hash[((1) << (i))] = i;
}
void initBcnt(int n, int bcnt[]) {
  bcnt[0] = 0;
  for (int i = 1; i < ((1) << (n)); i++)
    bcnt[i] = bcnt[i ^ ((((i) ^ ((i)-1)) & i))] + 1;
}
int print(int aa[]) { return 0; }
template <typename T>
vector<pair<T, T> > interval_union(vector<pair<T, T> > all) {
  vector<pair<T, T> > res;
  if (all.empty()) return res;
  sort(all.begin(), all.end());
  res.push_back(all[0]);
  for (int i = 1; i < all.size(); i++) {
    if (all[i].first <= res.back().second) {
      res.back().second = max(res.back().second, all[i].second);
    } else {
      res.push_back(all[i]);
    }
  }
  return res;
}
template <typename T>
class CPoint : public complex<T> {
 public:
  CPoint(const T& x = T(), const T& y = T()) : complex<T>(x, y){};
  T& x() { return complex<T>::real(); }
  T& y() { return complex<T>::imag(); }
};
template <typename T>
vector<T> set_diff(vector<T>& a, vector<T>& b) {
  vector<T> c;
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  set_difference(a.begin(), a.end(), b.begin(), b.end(),
                 inserter(c, c.begin()));
  return c;
}
template <typename T>
ostream& operator<<(ostream& out, const valarray<T>& val) {
  for (int i = 0; i < val.size(); i++) {
    cout << val[i] << " ";
  }
  return out;
}
vector<string> transpose(const vector<string>& grid) {
  vector<string> res((grid[0].size()), string((grid.size()), ' '));
  for (int i = 0; i < grid.size(); i++)
    for (int j = 0; j < grid[i].size(); j++) {
      res[j][i] = grid[i][j];
    }
  return res;
}
double nextGaussian() {
  double x, y, r;
  for (;;) {
    x = 2.0 * rand() / (RAND_MAX + 1.0) - 1.0;
    y = 2.0 * rand() / (RAND_MAX + 1.0) - 1.0;
    r = x * x + y * y;
    if (r >= 1.0) continue;
    break;
  }
  double re = sqrt(-2.0 * log(r) / (r)) * x;
  return re;
}
const int N = 100000;
int dp[N + 1], prefix[N + 1];
int win[N + 1];
int used[2 * N];
int main() {
  int n, s;
  cin >> n;
  for (typeof(2) x = 2; x < n + 1; ++x) {
    int m = 2 * x;
    win[x] = x + 1;
    int B = sqrt(1.0 * m) + 1;
    while (B * B > m) B--;
    int lower = n + 1;
    for (int b = 2; b <= B; b++)
      if (0 == (m % b)) {
        int a = m / b - b + 1;
        if (0 == (a & 1)) {
          a >>= 1;
          used[s = (prefix[a + b - 1] ^ prefix[a - 1])] = x;
          if (s == 0) win[x] = min(win[x], b);
          lower = lower > s ? s : lower;
        }
      }
    int& p = dp[x];
    if (lower)
      p = 0;
    else
      for (p = 0; used[p] == x; p++)
        ;
    prefix[x] = prefix[x - 1] ^ dp[x];
  }
  cout << (dp[n] ? win[n] : -1) << endl;
  return 0;
}
