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"
using namespace std;

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
typedef long long int ll;
typedef pair<ll, ll> P; typedef pair<ll, P> T;
typedef complex<double> com;
struct edge { int u, v, cost; };
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (!b)return a; else return gcd(b, a % b); }
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
int mod = 1e9 + 7; //998244353;
struct Mint {
	int val;
	Mint inv() const {
		unsigned tmp, a = val, b = mod; int x = 1, y = 0;
		while (b) tmp = a / b, a -= tmp * b, swap(a, b), x -= tmp * y, swap(x, y);
		return Mint(x);
	}
public:
	Mint() :val(0) {}
	Mint(ll x) :val(x >= 0 ? x % mod : x % mod + mod) {}
	int mtoi() { return this->val; }
	Mint pow(ll t) { Mint res = 1; while (t > 0) { if (t & 1) res *= *this; *this *= *this; t >>= 1; }return res; }
	Mint& operator+=(const Mint& x) { if ((val += x.val) >= mod) val -= mod; return *this; }
	Mint& operator-=(const Mint& x) { if ((val += mod - x.val) >= mod) val -= mod; return *this; }
	Mint& operator*=(const Mint& x) { val = (ll)val * x.val % mod; return *this; }
	Mint& operator/=(const Mint& x) { return *this *= x.inv(); }
	bool operator==(const Mint& x) const { return val == x.val; }
	bool operator!=(const Mint& x) const { return val != x.val; }
	bool operator<(const Mint& x) const { return val < x.val; }
	bool operator<=(const Mint& x) const { return val <= x.val; }
	bool operator>(const Mint& x) const { return val > x.val; }
	bool operator>=(const Mint& x) const { return val >= x.val; }
	Mint operator-() const { return Mint(-val); }
	Mint operator+(const Mint& x) const { return Mint(*this) += x; }
	Mint operator-(const Mint& x) const { return Mint(*this) -= x; }
	Mint operator*(const Mint& x) const { return Mint(*this) *= x; }
	Mint operator/(const Mint& x) const { return Mint(*this) /= x; }
};
struct factorial {
	vector<Mint> Fact, Finv;
public:
	factorial(int maxx) {
		Fact.resize(maxx + 1, Mint(1)); Finv.resize(maxx + 1);
		rep(i, 0, maxx) Fact[i + 1] = Fact[i] * Mint(i + 1);
		Finv[maxx] = Mint(1) / Fact[maxx];
		rrep(i, maxx, 0) Finv[i - 1] = Finv[i] * Mint(i);
	}
	Mint fact(int n) { return Fact[n]; }
	Mint finv(int n) { return Finv[n]; }
	Mint nCr(int n, int r) {
		if (n < 0 || n < r || r < 0) return Mint(0);
		return Fact[n] * Finv[r] * Finv[n - r];
	}
	Mint nPr(int n, int r) {
		if (n < 0 || n < r || r < 0) return Mint(0);
		return Fact[n] * Finv[n - r];
	}
};
class UnionFind {
	vector<int> par;
public:
	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 max_flow {
	struct Edge { int to, cap, rev; };
	int V; vector<vector<Edge>> G; vector<int> itr, level;
public:
	max_flow(int V) : V(V) { G.assign(V, vector<Edge>()); }
	void add_edge(int from, int to, int cap) {
		G[from].push_back({ to, cap, (int)G[to].size() });
		G[to].push_back({ from, 0, (int)G[from].size() - 1 });
	}
	void bfs(int s) {
		level.assign(V, -1); queue<int> q;
		level[s] = 0; q.push(s);
		while (!q.empty()) {
			int v = q.front(); q.pop();
			for (auto& e : G[v]) {
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}
	int dfs(int v, int t, int f) {
		if (v == t) return f;
		for (int& i = itr[v]; i < (int)G[v].size(); ++i) {
			Edge& e = G[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d, G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	int run(int s, int t) {
		int ret = 0, f;
		while (bfs(s), level[t] >= 0) {
			itr.assign(V, 0);
			while ((f = dfs(s, t, inf)) > 0) ret += f;
		}
		return ret;
	}
};
vector<ll> dijkstra(vector<vector<edge>> Grp, int s) {
	priority_queue<P, vector<P>, greater<P> > que;
	vector<ll> dist(Grp.size(), INF); dist[s] = 0; que.push(P(0, s));
	while (!que.empty()) {
		P p = que.top(); que.pop();
		int v = p.second; if (dist[v] < p.first) continue;
		rep(i, 0, Grp[v].size()) {
			edge e = Grp[v][i];
			if (dist[e.v] > dist[v] + e.cost) {
				dist[e.v] = dist[v] + e.cost;
				que.push(P(dist[e.v], e.v));
			}
		}
	} return dist;
}
void fft(vector<com>& x, bool inv) {
	int s = x.size(); if (s == 1) return;
	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);
	rep(i, 0, s)x[i] = even[i % (s / 2)] + w * odd[i % (s / 2)], w *= w_0;
}
void MultiFunction(vector<int>& a, vector<int>& b) {
	int n = a.size(), maxx = 1; while (maxx <= 2 * n)maxx *= 2;
	vector<com> x(maxx), y(maxx);
	rep(i, 0, n) x[i] = com(a[i], 0), y[i] = com(b[i], 0);
	fft(x, 0), fft(y, 0); rep(i, 0, maxx) x[i] *= y[i];
	fft(x, 1); rep(i, 0, maxx)x[i] /= maxx;
	a.resize(2 * n - 1, 0);
	rep(i, 0, 2 * n - 1)a[i] = (int)(x[i].real() + 0.5);
}
ll merge_cnt(vector<int> a) {
	ll n = a.size(), ai = 0, bi = 0, ci = 0, cnt = 0;
	if (n <= 1) return 0;
	vector<int> b(a.begin(), a.begin() + n / 2);
	vector<int> c(a.begin() + n / 2, a.end());
	cnt += merge_cnt(b) + merge_cnt(c);
	while (ai < n) {
		if (bi < b.size() && (ci == c.size() || b[bi] <= c[ci]))a[ai++] = b[bi++];
		else cnt += n / 2LL - bi, a[ai++] = c[ci++];
	}
	return cnt;
}
//template end



int main() {
	int n; cin >> n;
	int x[] = { 1, 2, 4, 7, 12, 20, 29, 38, 52, 73 };
	ll a[11][11] = {};
	a[0][1] = a[1][0] = 1;
	ll m = 1;
	rep(rot, 2, n) {
		rep(i, 0, rot)a[i][rot] = a[rot][i] = (m + 1) * x[i];
		vector<int> f(rot+1);
		rep(i, 0, rot+1)f[i] = i;
		do{
			ll s = 0;
			rep(i, 0, rot) s += a[f[i]][f[i+1]];
			chmax(m, s);
		} while (next_permutation(f.begin(),f.end()));
	}
	rep(i, 0, n) {
		rep(j, 0, n)printf("%lld ", a[i][j]);
		printf("\n");
	}
	return 0;
}