Problem: Diverta City is a new city consisting of N towns numbered 1, 2, ..., N.

The mayor Ringo is planning to connect every pair of two different towns with a bidirectional road. The length of each road is undecided.

A Hamiltonian path is a path that starts at one of the towns and visits each of the other towns exactly once. The reversal of a Hamiltonian path is considered the same as the original Hamiltonian path.

There are N! / 2 Hamiltonian paths. Ringo wants all these paths to have distinct total lengths (the sum of the lengths of the roads on a path), to make the city diverse.

Find one such set of the lengths of the roads, under the following conditions:

* The length of each road must be a positive integer.
* The maximum total length of a Hamiltonian path must be at most 10^{11}.

Constraints

* N is a integer between 2 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:


N


Output

Print a set of the lengths of the roads that meets the objective, in the following format:


w_{1, 1} \ w_{1, 2} \ w_{1, 3} \ ... \ w_{1, N}
w_{2, 1} \ w_{2, 2} \ w_{2, 3} \ ... \ w_{2, N}
:  :     :
w_{N, 1} \ w_{N, 2} \ w_{N, 3} \ ... \ w_{N, N}


where w_{i, j} is the length of the road connecting Town i and Town j, which must satisfy the following conditions:

* w_{i, i} = 0
* w_{i, j} = w_{j, i} \ (i \neq j)
* 1 \leq w_{i, j} \leq 10^{11} \ (i \neq j)



If there are multiple sets of lengths of the roads that meet the objective, any of them will be accepted.

Examples

Input

3


Output

0 6 15
6 0 21
15 21 0


Input

4


Output

0 111 157 193
111 0 224 239
157 224 0 258
193 239 258 0

Solution (in CPP):

Solution:
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
typedef long long ll;

ll ans[11][11][11] = {
  {}, // 0
  {}, // 1
  { // 2
    {0, 1},
    {1, 0}
  },
  { // 3
    {0, 1, 2},
    {1, 0, 3},
    {2, 3, 0},
  },
  { // 4
    {0, 1, 2, 3},
    {1, 0, 4, 7},
    {2, 4, 0, 12},
    {3, 7, 12, 0}
  },
  { // 5
    {0LL, 1LL, 2LL, 3LL, 5LL},
    {1LL, 0LL, 6LL, 12LL, 21LL},
    {2LL, 6LL, 0LL, 33LL, 59LL},
    {3LL, 12LL, 33LL, 0LL, 107LL},
    {5LL, 21LL, 59LL, 107LL, 0LL}
  },
  { // 6
    {0LL, 1LL, 2LL, 3LL, 5LL, 8LL},
    {1LL, 0LL, 9LL, 18LL, 33LL, 57LL},
    {2LL, 9LL, 0LL, 88LL, 171LL, 313LL},
    {3LL, 18LL, 88LL, 0LL, 513LL, 985LL},
    {5LL, 33LL, 171LL, 513LL, 0LL, 1813LL},
    {8LL, 57LL, 313LL, 985LL, 1813LL, 0LL}
  },
  { // 7
    {0LL, 1LL, 2LL, 3LL, 5LL, 8LL, 13LL},
    {1LL, 0LL, 14LL, 33LL, 58LL, 101LL, 160LL},
    {2LL, 14LL, 0LL, 251LL, 476LL, 861LL, 1472LL},
    {3LL, 33LL, 251LL, 0LL, 2416LL, 4777LL, 8566LL},
    {5LL, 58LL, 476LL, 2416LL, 0LL, 14624LL, 28334LL},
    {8LL, 101LL, 861LL, 4777LL, 14624LL, 0LL, 52087LL},
    {13LL, 160LL, 1472LL, 8566LL, 28334LL, 52087LL, 0LL}
  },
  { // 8
    {0LL, 1LL, 2LL, 3LL, 5LL, 8LL, 13LL, 21LL},
    {1LL, 0LL, 16LL, 44LL, 71LL, 133LL, 217LL, 369LL},
    {2LL, 16LL, 0LL, 547LL, 1089LL, 2064LL, 3448LL, 5871LL},
    {3LL, 44LL, 547LL, 0LL, 8184LL, 17347LL, 28671LL, 53079LL},
    {5LL, 71LL, 1089LL, 8184LL, 0LL, 87173LL, 174210LL, 329503LL},
    {8LL, 133LL, 2064LL, 17347LL, 87173LL, 0LL, 570121LL, 1014448LL},
    {13LL, 217LL, 3448LL, 28671LL, 174210LL, 570121LL, 0LL, 1933928LL},
    {21LL, 369LL, 5871LL, 53079LL, 329503LL, 1014448LL, 1933928LL, 0LL}
  },
  { // 9
    {0LL, 1LL, 2LL, 3LL, 5LL, 8LL, 13LL, 21LL, 34LL},
    {1LL, 0LL, 35LL, 81LL, 127LL, 214LL, 352LL, 587LL, 953LL},
    {2LL, 35LL, 0LL, 1332LL, 2660LL, 5107LL, 8608LL, 12288LL, 21965LL},
    {3LL, 81LL, 1332LL, 0LL, 34689LL, 67572LL, 130934LL, 228030LL, 384742LL},
    {5LL, 127LL, 2660LL, 34689LL, 0LL, 639008LL, 1245184LL, 2487343LL, 4177264LL},
    {8LL, 214LL, 5107LL, 67572LL, 639008LL, 0LL, 7061377LL, 14188610LL, 28067969LL},
    {13LL, 352LL, 8608LL, 130934LL, 1245184LL, 7061377LL, 0LL, 46572628LL, 81788920LL},
    {21LL, 587LL, 12288LL, 228030LL, 2487343LL, 14188610LL, 46572628LL, 0LL, 132595451LL},
    {34LL, 953LL, 21965LL, 384742LL, 4177264LL, 28067969LL, 81788920LL, 132595451LL, 0LL},
  },
  { // 10
{0LL, 1LL, 2LL, 3LL, 5LL, 8LL, 13LL, 21LL, 34LL, 48LL},
{1LL, 0LL, 49LL, 129LL, 184LL, 331LL, 526LL, 897LL, 1450LL, 2334LL},
{2LL, 49LL, 0LL, 3590LL, 7216LL, 13913LL, 23502LL, 40969LL, 67850LL, 96252LL},
{3LL, 129LL, 3590LL, 0LL, 164224LL, 303104LL, 572928LL, 998968LL, 1682240LL, 2791421LL},
{5LL, 184LL, 7216LL, 164224LL, 0LL, 4558912LL, 8910819LL, 17380608LL, 29359616LL, 50253536LL},
{8LL, 331LL, 13913LL, 303104LL, 4558912LL, 0LL, 82435150LL, 163244031LL, 327165975LL, 544567680LL},
{13LL, 526LL, 23502LL, 572928LL, 8910819LL, 82435150LL, 0LL, 937430049LL, 1598799868LL, 3085697000LL},
{21LL, 897LL, 40969LL, 998968LL, 17380608LL, 163244031LL, 937430049LL, 0LL, 5303799809LL, 9996473518LL},
{34LL, 1450LL, 67850LL, 1682240LL, 29359616LL, 327165975LL, 1598799868LL, 5303799809LL, 0LL, 15031992320LL},
{48LL, 2334LL, 96252LL, 2791421LL, 50253536LL, 544567680LL, 3085697000LL, 9996473518LL, 15031992320LL, 0LL},
  }
};


bool check(int n) {
  int perm[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  set<ll> ss;
  do {
    if(perm[0] > perm[n-1]) {
      continue;
    }
    ll d = 0;
    // REP(i, n) {
    //   cerr << perm[i] << " ";
    // }
    // cerr << endl;
    REP(i, n-1) {
      d += ans[n][perm[i]][perm[i+1]];
    }
    // cerr << "d = " << d << endl;
    if(ss.count(d) > 0) {
      // cerr << d << "!!!!!!!" << endl;
      return false;
    }
    ss.insert(d);
  } while(next_permutation(perm, perm + n));
  return true;
}


// // 初期用の吐くやつ
// int main0(void) {
//   int n = 4;
//   ll k = 0;
//   REP(i, n) {
//     printf("{");
//     REP(j, n) {
//       if(i != j && ans[n][i][j] == 0) {
//         ans[n][i][j] = ans[n][j][i] = 1LL << k;
//         ++k;
//       }
//       printf("%lldLL%s", ans[n][i][j], j == n-1 ? "},\n" : ", ");
//     }
//   }
//   return 0;
// }

// int main1(void) {
//   int n = 9;
//   assert(check(n));
//   ll last = 0;
//   REP(i, n) {
//     for(int j = i+1; j < n; ++j) {
//       cerr << "(" << i << "," << j << ")" << endl;
//       ll left = last;
//       ll right = ans[n][i][j];
//       while(left + 1 < right) {
//         ll md = (left + right) / 2;
//         ans[n][i][j] = ans[n][j][i] = md;
//         if(check(n)) {
//           right = md;
//         } else {
//           left = md;
//         }
//       }
//       ans[n][j][i] = ans[n][i][j] = right;
//     }
//   }
//   printf("Ans for %d\n", n);
//   REP(i, n) {
//     printf("{");
//     REP(j, n) {
//       printf("%lldLL%s", ans[n][i][j], j == n-1 ? "},\n" : ", ");
//     }
//   }
//   return 0;
// }


int main(void) {
  int n;
  cin >> n;
  REP(i, n) {
    REP(j, n) {
      printf("%lld%c", ans[n][i][j], j == n-1 ? '\n' : ' ');
    }
  }
  return 0;
}