Problem: We have an N×N checkerboard.

From the square at the upper left corner, a square that is i squares to the right and j squares below is denoted as (i, j). Particularly, the square at the upper left corner is denoted as (0, 0).

Each square (i, j) such that i+j is even, is colored black, and the other squares are colored white.

We will satisfy the following condition by painting some of the white squares:

* Any black square can be reached from square (0, 0) by repeatedly moving to a black square that shares a side with the current square.



Achieve the objective by painting at most 170000 squares black.

Constraints

* 1 \leq N \leq 1,000

Input

The input is given from Standard Input in the following format:


N


Output

Print the squares to paint in the following format:


K
x_1 y_1
x_2 y_2
:
x_K y_K


This means that a total of K squares are painted black, the i-th of which is (x_i, y_i).

Judging

The output is considered correct only if all of the following conditions are satisfied:

* 0 \leq K \leq 170000
* 0 \leq x_i, y_i \leq N-1
* For each i, x_i + y_i is odd.
* If i \neq j, then (x_i, y_i) \neq (x_j, y_j).
* The condition in the statement is satisfied by painting all specified squares.

Examples

Input

2


Output

1
1 0


Input

4


Output

3
0 1
2 1
2 3

Solution (in CPP):

Solution:
/* -------------------------------- Template -------------------------------- */
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
 
using ll = long long;
using ld = long double;
 
template <typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }
 
template<typename T> constexpr T inf = [](){ assert(false); };
// template<> constexpr int inf<int> = 1e9;
// template<> constexpr ll inf<ll> = 1e18;
// template<> constexpr ld inf<ld> = 1e30;
 
struct yes_no : std::numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};
 
void solve();
 
int main() {
  std::locale loc(std::locale(), new yes_no);
  std::cout << std::boolalpha << std::setprecision(12) << std::fixed;
  std::cout.imbue(loc);
  solve();
  return 0;
}
 
using namespace std;
 
/* -------------------------------- Library -------------------------------- */
 
class UnionFind {
  vector<int> p;
public:
  UnionFind (int n) : p(n, -1) {}
  int root(int x) {
    return p[x] < 0 ? x : p[x] = root(p[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (p[y] < p[x]) swap(x, y);
    if (p[x] == p[y]) --p[x];
    p[y] = x;
    return true;
  }
};
 
/* ---------------------------------- Main ---------------------------------- */
 
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
 
int n;
 
int get_id(int i, int j) {
  return i * n + j;
}
 
void solve() {
  cin >> n;
  UnionFind uf(n * n);
  vector<pair<int,int>> res;
  for (int num = 4; num >= 2; --num) {
    REP(i,n) REP(j,n) {
      if ((i + j) % 2 == 0) continue;
      set<int> roots;
      vector<int> x;
      REP(dir,4) {
        int ni = i + dx[dir];
        int nj = j + dy[dir];
        if (ni < 0 || nj < 0 || ni >= n || nj >= n) continue;
        x.push_back(get_id(ni, nj));
      }
      for (int k: x) {
        roots.insert(uf.root(k));
      }
      if (int(roots.size()) >= num) {
        res.emplace_back(i, j);
        for (int k: x) {
          uf.unite(k, x[0]);
        }
      }
    }
  }
  cout << res.size() << endl;
  for (auto p: res) cout << p.first << " " << p.second << endl;
  return;
}