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:
////////////////////////////////////////////
///                                      ///
///         Template ver. 1 rapel        ///
/// Fear is Temporary, Regret is Forever ///
///          Must Try and Get AC         ///
///                                      ///
////////////////////////////////////////////
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <iomanip>
 
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <utility>
 
#include <math.h>
#include <complex>
 
#include <assert.h>
#include <time.h>
//#include <chrono>
//#include <random>
 
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <bitset>
 
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define endl '\n'
using namespace std;
 
typedef long long LL;
typedef unsigned long long ULL;
 
void desperate_optimization(int precision){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cout.setf(ios::fixed);
  	cout.setf(ios::showpoint);
  	cout.precision(precision);
}
 
const int N = 10;
LL arr[N + 5][N + 5];
set<int> st;
set<int> nx;
vector<int> vec;
 
void hora(int tc) {
	int n;
	cin>>n;
	st.insert({1, 2, 4, 7, 12, 20, 29, 38, 52, 73});
//	for(int i = 1;i < n;i++) {
//		nx.clear();
//		for(auto x: st) {
//			nx.insert(x);
//			for(auto y: st) {
//				if(x == y) continue;
//				nx.insert(x + y);
//			}
//		}
//		int mx = -1;
//		int now = 0;
//		for(auto x: nx) {
//			if(x != now + 1) {
//				mx = now + 1;
//				break;
//			}
//			now = x;
//		}
//		if(mx == -1) mx = now + 1;
//		st.insert(mx);		
//	}
//	for(auto x: st) cout<<x<<endl;
	LL maxi = 0;
	vec.PB(0);
	for(int i = 1;i < n;i++) {
		int j = 0;
		for(auto x: st) {
			if(i == j) break;
			arr[i][j] = arr[j][i] = (maxi + 1) * x;
			j++;
		}
		vec.PB(i);
		sort(vec.begin(), vec.end());
		do{
			LL tots = 0;
			for(int i = 1;i < vec.size();i++) tots += arr[vec[i - 1]][vec[i]];
			maxi = max(maxi, tots);
		}while(next_permutation(vec.begin(), vec.end()));
	}
	for(int i = 0;i < n;i++) {
		for(int j = 0;j < n;j++) {
			if(j) cout<<" ";
			cout<<arr[i][j];
		}
		cout<<endl;
	}
}
 
int main(){
	desperate_optimization(10);
	int ntc = 1;
	//cin>>ntc;
	for(int tc = 1;tc <= ntc;tc++) hora(tc);
	return 0;
}