Description

Assume there are $n$ rods. We insert balls labeled $1$, $2$, $3$, ... into these $n$ rods in order, following the rules below:

1. Each time, you can only place a ball on the top of some rod.
2. On the same rod, the sum of the labels of any $2$ adjacent balls is a perfect square.

Design an algorithm to compute the maximum number of balls that can be placed on $n$ rods. For example, with $4$ rods, at most $11$ balls can be placed.

Given $n$, compute the maximum number of balls that can be placed on $n$ rods.

Input Format

There is only one line containing an integer $n$, representing the number of rods.

Output Format

This problem has a Special Judge.

Please output the maximum number of balls that can be placed on $n$ rods, along with a corresponding placement scheme.

The first line is the number of balls.

The next $n$ lines each contain several integers, representing the labels of the balls on one rod, separated by a single space.

4

11
1 8
2 7 9
3 6 10
4 5 11

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 55$.

Translated by ChatGPT 5