Princess Bala and Z founded a new colony where ants are free to express their own beliefs. The new colony, however, now faces a serious threat to its survival. Acid-shooting termites have become stronger and are willing to attack the nest.

Z needs to develop a defence strategy for the colony. Queen Ant, Princess Bala's mother, tells him that at least twelve ants are needed to successfully kill a single termite. Unfortunately, the number of soldiers has had a significant decrease since the new freedom ideals were spread out. Thus, he decides that no more ants than needed will participate in the battle.

In order to create a safety perimeter, soldiers need to be set in concentric rings around the colony's nest. The number of warriors of the innermost ring must be a multiple of four. Besides, to coordinate the defence each ring must have exactly 8 ants more than the ring it surrounds. Taking into account these constraints, the number of rings must be as large as possible.

Z's friend, Weaver, has been sent to the enemy's territory to spy them and gather vital information about their plans. Being successful, he will inform Z the exact number of warriors they are going to send. Given this information Ant Z needs all the help you can provide him to determine the best deployment for his troops.

Input

The input consists of several test cases, each one in a single line. Each test case consists of the number of termites n (1 <= n < 2³²) willing to attack the nest. The input terminates when n = 0.

Output

For each test case, indicate the number of soldiers needed on the outmost defence ring.

Example

Input:
1
2
33
0

Output:
12
16
76