Walk Alone is an expert in dynamic programming, but he gets bored with traditional dynamic programming problem like counting paths on a 2-dimension grid, so he wants to do it in reverse. The problem he raised is as follows:
On a 2-dimension grid of size $$$n \times n$$$, originally you are on grid $$$(1,1)$$$. The grid consists of $$$0$$$ and $$$1$$$, and you can only walk on the grid with number $$$1$$$ in it. You can only go down or right, i.e. you can only increase your $$$x$$$ or $$$y$$$ by one. Also you cannot walk outside the grid.
Given the number $$$x$$$ of ways to walk from $$$(1,1)$$$ to $$$(n,n)$$$, you need to construct a grid of $$$n \times n$$$ so that the ways to walk is exactly $$$x$$$. However, since Walk Alone's brain is too small to memorize such a big grid, you need to guarantee that the size of the grid $$$n$$$ is equal to or smaller than $$$30$$$.
The only line of the input contains one integer $$$x$$$ ($$$1 \le x \le 10^9$$$), denoting the ways to walk.
The first line of the output contains the size of the grid $$$n$$$. Remind that you need to guarantee $$$1 \le n \le 30$$$.
The following $$$n$$$ lines each contains $$$n$$$ integers $$$a_{i,j} \in \{0,1\}$$$ denoting the grid, where $$$0$$$ denotes you cannot walk on the grid while $$$1$$$ is on the contrast.
3
3 1 1 0 1 1 0 1 1 1
10
4 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
