AtCoder's head office consists of N rooms numbered 1 to N. For any two rooms, there is a direct passage connecting these rooms.

For security reasons, Takahashi the president asked you to set a level for every passage, which is a positive integer and must satisfy the following condition:

* For each room i\ (1 \leq i \leq N), if we leave Room i, pass through some passages whose levels are all equal and get back to Room i, the number of times we pass through a passage is always even.



Your task is to set levels to the passages so that the highest level of a passage is minimized.

Constraints

* N is an integer between 2 and 500 (inclusive).

Input

Input is given from Standard Input in the following format:


N


Output

Print one way to set levels to the passages so that the objective is achieved, as follows:


a_{1,2} a_{1,3} ... a_{1,N}
a_{2,3} ... a_{2,N}
.
.
.
a_{N-1,N}


Here a_{i,j} is the level of the passage connecting Room i and Room j.

If there are multiple solutions, any of them will be accepted.

Example

Input

3


Output

1 2
1
N=int(input())
que=[[i for i in range(N)]]

ans={(i,j):-1 for i in range(N) for j in range(N)}

def classified(session):
    global que
    sub=[]
    while que:
        list=que.pop()
        n=len(list)
        if n!=1:
            left=list[:n//2]
            right=list[n//2:]
            for i in left:
                for j in right:
                    ans[(i,j)]=session
            sub.append(left)
            sub.append(right)
    que=sub

session=1
while que:
    classified(session)
    session+=1



Ans=[[] for i in range(N-1)]
for i in range(N-1):
    for j in range(i+1,N):
        Ans[i].append(ans[(i,j)])

for i in range(N-1):
    print(*Ans[i])