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:
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef complex<double> com;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int inf = 2e9;

//template

class UnionFind {
public:
	vector<int> par;
	UnionFind(int n) {
		par = vector<int>(n, -1);
	}
	int root(int a) {
		if (par[a] < 0) {
			return a;
		}
		else {
			return par[a] = root(par[a]);
		}
	}
	int size(int a) {
		return -par[root(a)];
	}
	bool connect(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b) {
			return false;
		}
		if (size(a) < size(b)) {
			swap(a, b);
		}
		par[a] += par[b];
		par[b] = a;
		return true;
	}
};
struct edge { int cost, u, v; };
bool comp(edge& e1,edge& e2){return e1.cost < e2.cost;}
#define MAX_E 200010
edge es[MAX_E]; int V,E;
int kruskal() {
	sort(es, es + E, comp);
	UnionFind uni(V);
	int res = 0;
	rep(i, 0, E) {
		edge e = es[i];
		if (uni.root(e.u) != uni.root(e.v)) {
			uni.connect(e.u, e.v);
			res += e.cost;
		}
	}
	return res;
}
ll mpow(ll a,ll b) {
	ll r = 1; a %= mod;
	while (b) {
		r = r * ((b % 2) ? a : 1) % mod;
		a = a * a % mod, b >>= 1;
	}
	return r;
}
vector<ll> fac, finv;
void factor(int N) {
	fac.resize(N); finv.resize(N);
	fac[0] = finv[0] = 1;
	rep(i, 1, N)fac[i] = 1LL * fac[i - 1] * i % mod;
	finv[N - 1] = mpow(fac[N - 1], mod - 2);
	for (int i = N - 2; i; --i) finv[i] = 1LL * finv[i + 1] * (i + 1) % mod;
}
int nCr(int n, int m) {
	if (m < 0 || n < m) return 0;
	return 1LL * (1LL * fac[n] * finv[m] % mod) * finv[n - m] % mod;
}
ll merge_cnt(vector<int>& a) {
	int n = a.size();
	if (n <= 1) return 0;
	ll cnt = 0;
	vector<int> b(a.begin(), a.begin() + n / 2);
	vector<int> c(a.begin() + n / 2, a.end());
	cnt += merge_cnt(b);
	cnt += merge_cnt(c);
	int ai = 0, bi = 0, ci = 0;
	while (ai < n) {
		if (bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) {
			a[ai++] = b[bi++];
		}
		else {
			cnt += n / 2 - bi;
			a[ai++] = c[ci++];
		}
	}
	return cnt;
}
void fft(vector<com>& x, bool inv) {
	int s = x.size();
	if (s == 1) return;
	else {
		vector<com> even(s / 2), odd(s / 2);
		rep(i, 0, s / 2) {
			even[i] = x[i * 2];
			odd[i] = x[i * 2 + 1];
		}
		fft(even, inv);
		fft(odd, inv);
		com w = 1, w_0 = polar(1.0, (inv ? -1 : 1) * 2LL * M_PI / s);
		int t = s / 2 - 1;
		rep(i, 0, s) {
			x[i] = even[i & t] + w * odd[i & t];
			w *= w_0;
		}
	}
}
#define MAX_V 100010
ll d[MAX_V];
void dijkstra(int s,const vector<vector<edge>>& G) {
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d, d + MAX_V, inf);
	d[s] = 0;
	que.push(P(0, s));
	while (!que.empty()) {
		P p = que.top();
		que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); ++i) {
			edge e = G[v][i];
			if (d[e.v] > d[v] + e.cost) {
				d[e.v] = d[v] + e.cost;
				que.push(P(d[e.v], e.v));
			}
		}
	}
}
bool cross(ll ax, ll ay, ll bx, ll by, ll cx, ll cy, ll dx, ll dy) {
	ll ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
	ll tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
	ll tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
	ll td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);
	return tc * td <= 0LL && ta * tb <= 0LL;
}
int diameter(const vector<vector<edge>>& g) {
	function<P(int, int)> dfs = [&](int prev, int v) {
		P r(0, v);
		rep(i, 0, g[v].size()) {
			edge e = g[v][i];
			if (e.v == prev) continue;
			P tmp = dfs(v, e.v);
			tmp.first += e.cost;
			if (r.first < tmp.first) r = tmp;
		}
		return r;
	};
	P r = dfs(-1, 0);
	P t = dfs(-1, r.second);
	return t.first;
}
int bipartite(const vector<vector<int>>& g) {
	int n = g.size();
	vector<int> color(n, -1);
	int white_cnt = 0;
	function<bool(int, int, int)> dfs = [&](int u, int prev, int c) {
		color[u] = c;
		if (c == 1) white_cnt++;
		for (auto v : g[u]) if (v != prev) {
			if (color[v] == -1) {
				if (!dfs(v, u, 1 - c)) return false;
			}
			else if (color[v] != 1 - c) {
				return false;
			}
		}
		return true;
	};
	if (!dfs(0, -1, 0)) return -1;
	return white_cnt;
}
//template end


int main() {
	int n; cin >> n;
	vector<vector<ll>> ans(n);
	rep(i, 0, n) ans[i].resize(n, 0);
	int a[10] = { 1,2,4,7,12,20,29,38,52,101 };
	int b[10] = { 1,2,4,7,12,20,30,39,67,101 };
	ll maxx = 1, sum = 0;
	rep(i, 0, n) {
		rep(j, i+1, n) {
			ans[j][i]=ans[i][j] = maxx * a[j-i-1];
		}
		maxx *= b[n-i-1];
	}
	rep(i, 0, n){
		rep(j, 0, n) {
			printf("%lld ", ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}