Queens

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2804
64-bit integer IO format: %I64d      Java class name: Main

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

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .