For Kisses

WisKey has a little lovely sister named Sweet. One day Sweet wants play a game with him. The game rules like this, in the N*N girds, you can choose K girds to make any 4 of grids not rectangles vertexes, Sweet say if WisKey can find out the max K, she will give him a Kiss !!
WoW, this is a funny and cute challenge, everybody rise UP~
This is not rectangle.
This is a rectangle.

The Sweet just has 9 questions, any questions have an N(N<=21). and WisKey want 9 Kisses!

For each questions, output the max possible K.

1
2
3
4
5
6
7
13
21

1
3
.
.
.

Hint
When N = 2, the one of the solutions is , so the max K is 3.

2009 Multi-University Training Contest 4 - Host by HDU