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:
// This code wrote by chtholly_micromaker(MicroMaker)
#pragma GCC optimize("Ofast,O3,inline")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define reg register
#define int long long
#define ALL(x) (x).begin(),(x).end()
#define mem(x,y) memset(x,y,sizeof x)
#define sz(x) (int)(x).size()
#define ln puts("")
#define lsp putchar(32)
#define pb push_back
#define MP make_pair
#define dbg(x) cerr<<">"<<__func__<<"\tLine: "<<__LINE__<<' '<<#x<<": "<<x<<endl
using namespace std;
template <class t> inline void read(t &s){s=0;
reg int f=1;reg char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;}
template<class t,class ...A> inline void read(t &x,A &...a){read(x);read(a...);}
template <class t> inline void write(t x){if(x<0)putchar('-'),x=-x;
int buf[21],top=0;while(x)buf[++top]=x%10,x/=10;if(!top)buf[++top]=0;
while(top)putchar(buf[top--]^'0');return;}
inline void setIn(string s){freopen(s.c_str(),"r",stdin);return;}
inline void setOut(string s){freopen(s.c_str(),"w",stdout);return;}
inline void setIO(string s=""){setIn(s+".in");setOut(s+".out");return;}
template <class t>inline bool checkmin(t&x,t y){if(x>y){x=y;return 1;}return 0;}
template <class t>inline bool checkmax(t&x,t y){if(x<y){x=y;return 1;}return 0;}
inline int lowbit(int x){return x&(-x);}
int f[15];
int w[150][150];
inline void Init()
{
	map<int,int> dr;
	dr[3];
	f[1]=1,f[2]=2;
	for(int i=3;i<=11;++i)
	{
		for(int j=dr[i-1]+1;;++j)
		{
			if(dr.count(j))
				continue;
			reg bool flg=true;
			for(int k=1;k<i;++k)
				if(dr.count(j+f[k]))
				{
					flg=false;
					break;
				}
			if(!flg)
				continue;
			f[i]=j;
			for(int k=1;k<i;++k)
				dr[j+f[k]];
			break;
		}
	}
	return;
}
int idx[15];
signed main(void)
{
	Init();
	int n;read(n);
	for(int i=2;i<=n;++i)
	{
		reg int maxi=0;
		for(int j=1;j<i;++j)
			idx[j]=j;
		do
		{
			reg int sum=0;
			for(int j=1;j<i-1;++j)
				sum+=w[idx[j]][idx[j+1]];
			checkmax(maxi,sum);
		}while(next_permutation(idx+1,idx+i));
		for(int j=1;j<i;++j)
			w[i][j]=w[j][i]=(maxi+1)*f[j];
	}
	for(int i=1;i<=n;++i,ln)
		for(int j=1;j<=n;++j)
			write(w[i][j]),lsp;
	return 0;
}

/*
 * Check List:
 * 1. Input / Output File (USACO and OI and UVa)
 * 2. long long 
 * 3. Special Test such as n=1
 * 4. Array Size
 * 5. Memory Limit (OI) int is 4 and longlong is 8
 * 6. Mod (a*b%p*c%p not a*b*c%p  ,  (a-b+p)%p not a-b )
 * 7. Name ( int k; for(int k...))
 * 8. more tests , (T=2 .. more)
 * 9. blank \n after a case
*/