Queens

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Everyone knows about the "eight queens problem", but today you will solve a different one.
We are given triangle lattice of side n, as shown in the Figure below. A queen on the lattice can move along a straight line parallel to any of the sides of the triangle. How many queens can be placed on the lattice at most, without any two queens attacking each other?

Input

Each test case contains a single integer N (1<=N<=10^10), indicating the side of the triangle. The input is terminated by a set starting with N = 0. This set should not be processed.

Output

For each test case, output on a line the number of the queens can be placed on the lattice without any two queens attacking each other.

Sample Input

1 2 0

Sample Output

1 1

Hint

lcy

Source

HDU 2009-4 Programming Contest

提交代码