Problem: Jzzhu has picked n apples from his big apple tree. All the apples are numbered from 1 to n. Now he wants to sell them to an apple store. 

Jzzhu will pack his apples into groups and then sell them. Each group must contain two apples, and the greatest common divisor of numbers of the apples in each group must be greater than 1. Of course, each apple can be part of at most one group.

Jzzhu wonders how to get the maximum possible number of groups. Can you help him?

Input

A single integer n (1 ≤ n ≤ 105), the number of the apples.

Output

The first line must contain a single integer m, representing the maximum number of groups he can get. Each of the next m lines must contain two integers — the numbers of apples in the current group.

If there are several optimal answers you can print any of them.

Examples

Input

6


Output

2
6 3
2 4


Input

9


Output

3
9 3
2 4
6 8


Input

2


Output

0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void _1() {
  int a[3], b[3], n;
  for (int& x : a) cin >> x;
  for (int& y : b) cin >> y;
  cin >> n;
  int cups = accumulate(a, a + 3, 0), medals = accumulate(b, b + 3, 0);
  int m = cups / 5 + ((cups % 5 == 0) ? 0 : 1) + medals / 10 +
          ((medals % 10 == 0) ? 0 : 1);
  if (n >= m)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}
void _2() {
  string s, t;
  cin >> s >> t;
  int n = s.length(), m = t.length();
  bool need_automaton = true, need_array = true, need_both = true;
  int i = 0, j = 0;
  while (i < n && j < m) {
    if (s[i] == t[j]) {
      ++i;
      ++j;
    } else {
      ++i;
    }
  }
  if (j != m) {
    need_automaton = false;
  }
  if (need_automaton) {
    cout << "automaton" << endl;
    return;
  }
  vector<int> s_cnt(26), t_cnt(26);
  for (int i = 0; i < n; ++i) {
    ++s_cnt[s[i] - 'a'];
  }
  for (int j = 0; j < m; ++j) {
    ++t_cnt[t[j] - 'a'];
  }
  for (int k = 0; k < 26; ++k) {
    if (s_cnt[k] != t_cnt[k]) {
      need_array = false;
      break;
    }
  }
  if (need_array) {
    cout << "array" << endl;
    return;
  }
  for (int k = 0; k < 26; ++k) {
    if (s_cnt[k] < t_cnt[k]) {
      need_both = false;
      break;
    }
  }
  if (need_both) {
    cout << "both" << endl;
    return;
  }
  cout << "need tree" << endl;
}
int _3_solve(int l, int r, int h, vector<int>& a) {
  if (l >= r) {
    return 0;
  }
  int x = *min_element(a.begin() + l, a.begin() + r);
  if (h >= x) {
    return 0;
  }
  int answer = x - h;
  int l_ = l;
  for (int i = l; i < r; ++i) {
    if (a[i] == x) {
      answer += _3_solve(l_, i, x, a);
      l_ = i + 1;
    }
  }
  answer += _3_solve(l_, r, x, a);
  return min(r - l, answer);
}
void _3() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  cout << _3_solve(0, n, 0, a) << endl;
}
long long _4_solve(long long x, int n, int m) {
  long long res = 0;
  for (int i = 1; i <= n; ++i) {
    res += min((long long)m, (x - 1) / i);
  }
  return res;
}
void _4() {
  int n, m;
  long long k;
  cin >> n >> m >> k;
  long long l = 1, r = (long long)n * m;
  while (l <= r) {
    long long x = (l + r) >> 1;
    if (_4_solve(x, n, m) < k) {
      l = x + 1;
    } else {
      r = x - 1;
    }
  }
  cout << l - 1 << endl;
}
int find_set(int v, vector<int>& p) {
  return (p[v] == v) ? v : p[v] = find_set(p[v], p);
}
void _5() {
  int n, m;
  cin >> n >> m;
  vector<int> p(n + 1);
  for (int i = 1; i <= n; ++i) {
    p[i] = i;
  }
  int x, y;
  for (int i = 1; i <= m; ++i) {
    cin >> x >> y;
    p[find_set(y, p)] = find_set(x, p);
  }
  long long answer = 1LL << n;
  for (int i = 1; i <= n; ++i) {
    if (find_set(i, p) == i) {
      answer >>= 1;
    }
  }
  cout << answer << endl;
}
void _6() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  int i_cnt, i_max_cnt = -1, i_last;
  for (int i = 0; i < n; ++i) {
    i_cnt = (a[i] + m - 1) / m;
    if (i_cnt >= i_max_cnt) {
      i_max_cnt = i_cnt;
      i_last = i;
    }
  }
  cout << i_last + 1 << endl;
}
const int MOD = 1000000007;
int n_th_number(int x, int y, int n) {
  int f1 = x, f2 = y;
  long long m[2][2] = {{0, 1}, {-1, 1}};
  long long res[2][2] = {{1, 0}, {0, 1}};
  long long buf[2][2] = {{0, 0}, {0, 0}};
  while (n) {
    if (n & 1) {
      for (long long i = (long long)0; i < (long long)2; ++i) {
        for (long long j = (long long)0; j < (long long)2; ++j) {
          buf[i][j] = 0;
          for (long long k = (long long)0; k < (long long)2; ++k) {
            buf[i][j] += (res[i][k] * m[k][j]);
          }
          buf[i][j] = (buf[i][j] % MOD + MOD) % MOD;
        }
      }
      for (long long i = (long long)0; i < (long long)2; ++i) {
        for (long long j = (long long)0; j < (long long)2; ++j) {
          res[i][j] = buf[i][j];
        }
      }
    }
    for (long long i = (long long)0; i < (long long)2; ++i) {
      for (long long j = (long long)0; j < (long long)2; ++j) {
        buf[i][j] = 0;
        for (long long k = (long long)0; k < (long long)2; ++k) {
          buf[i][j] += (m[i][k] * m[k][j]);
        }
        buf[i][j] = (buf[i][j] % MOD + MOD) % MOD;
      }
    }
    for (long long i = (long long)0; i < (long long)2; ++i) {
      for (long long j = (long long)0; j < (long long)2; ++j) {
        m[i][j] = buf[i][j];
      }
    }
    n >>= 1;
  }
  return ((res[0][0] * f1 + res[0][1] * f2) % MOD + MOD) % MOD;
}
void _7() {
  int x, y;
  cin >> x >> y;
  int n;
  cin >> n;
  int seq[6] = {x, y, y - x, -x, -y, -y + x};
  int ans = (seq[(n - 1) % 6] % MOD + MOD) % MOD;
  cout << ans << endl;
}
void _8() {
  int n, m, k;
  cin >> n >> m >> k;
  if (n + m - 2 < k) {
    cout << -1 << endl;
    return;
  }
  int x, y;
  long long opt1, opt2;
  x = min(k, n - 1);
  y = k - x;
  opt1 = (1LL * n / (x + 1)) * (1LL * m / (y + 1));
  y = min(k, m - 1);
  x = k - y;
  opt2 = (1LL * n / (x + 1)) * (1LL * m / (y + 1));
  cout << max(opt1, opt2) << endl;
}
struct edge {
  int v, w;
  bool is_train;
};
void _9() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<pair<int, int> > > g(n);
  int u, v, x;
  for (int i = 0; i < m; ++i) {
    cin >> u >> v >> x;
    --u;
    --v;
    g[u].push_back({v, x});
    g[v].push_back({u, x});
  }
  const long long oo = (1LL << 60);
  vector<long long> c(n, oo);
  int s, y;
  int ans = 0;
  for (int i = 0; i < k; ++i) {
    cin >> s >> y;
    --s;
    if (c[s] != oo) {
      ++ans;
    }
    c[s] = min(c[s], 1LL * y);
  }
  for (int i = 0; i < n; ++i) {
    if (c[i] != oo) {
      g[0].push_back({i, c[i]});
      g[i].push_back({0, c[i]});
    }
  }
  vector<long long> dist(n, oo);
  vector<int> in_degree(n);
  dist[0] = 0;
  set<pair<long long, int> > q;
  q.insert({0, 0});
  while (!q.empty()) {
    int u = q.begin()->second;
    q.erase(q.begin());
    for (auto e : g[u]) {
      if (dist[u] + e.second < dist[e.first]) {
        q.erase({dist[e.first], e.first});
        dist[e.first] = dist[u] + e.second;
        q.insert({dist[e.first], e.first});
        in_degree[e.first] = 1;
      } else if (dist[u] + e.second == dist[e.first]) {
        ++in_degree[e.first];
      }
    }
  }
  for (int i = 1; i < n; ++i) {
    if (c[i] == oo) {
      continue;
    }
    if (dist[i] < c[i] || (dist[i] == c[i] && in_degree[i] > 1)) {
      ++ans;
    }
  }
  cout << ans << endl;
}
void _10() {
  int n;
  cin >> n;
  vector<bool> is_prime(n + 1, true), is_used(n + 1, false);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; ++i) {
    if (!is_prime[i]) {
      continue;
    }
    for (int j = 2 * i; j <= n; j += i) {
      is_prime[j] = false;
    }
  }
  vector<pair<int, int> > answer;
  for (int i = n; i >= 2; --i) {
    if (!is_prime[i] || 2 * i > n) {
      continue;
    }
    vector<int> numbers;
    for (int j = i; j <= n; j += i) {
      if (!is_used[j]) {
        is_used[j] = true;
        numbers.push_back(j);
      }
    }
    if (numbers.size() % 2) {
      is_used[numbers[1]] = false;
      swap(numbers[1], numbers.back());
      numbers.pop_back();
    }
    for (int k = 0; k < numbers.size(); k += 2) {
      answer.push_back({numbers[k], numbers[k + 1]});
    }
  }
  cout << answer.size() << endl;
  for (auto e : answer) {
    cout << e.first << " " << e.second << endl;
  }
}
void DO_IT_NOW(int problem) {
  switch (problem) {
    case 1:
      _1();
      break;
    case 2:
      _2();
      break;
    case 3:
      _3();
      break;
    case 4:
      _4();
      break;
    case 5:
      _5();
      break;
    case 6:
      _6();
      break;
    case 7:
      _7();
      break;
    case 8:
      _8();
      break;
    case 9:
      _9();
      break;
    case 10:
      _10();
      break;
  }
}
int main() {
  cout << fixed << setprecision(10);
  ios::sync_with_stdio(false);
  DO_IT_NOW(10);
  return 0000000000000000000000000000000000000;
}