Pillars and Perfect Squares

Given n pillars, you are to place balls numbered 1, 2, 3, ... sequentially onto these pillars following the rules below:

1. Each ball can only be placed at the top of a pillar.
2. Within the same pillar, the sum of the numbers on any two adjacent balls must be a perfect square, i.e., it can be written as \(k^2\) for some positive integer \(k\).

Your task is to design an algorithm that computes the maximum number of balls that can be placed on the n pillars following these rules. For example, when n = 4, the maximum number of balls that can be placed is 11.

inputFormat

The input consists of a single integer n representing the number of pillars.

outputFormat

Output a single integer indicating the maximum number of balls that can be placed on the n pillars according to the rules.

sample

1

1