Two Knights

Your task is to count for $k=1,2,\dots ,nk=1,2,\backslash ldots,n$ the number of ways two knights can be placed on a $k\times kk\; \backslash times\; k$ chessboard so that they do not attack each other.

Input

The only input line contains an integer $nn$.

Output

Print $nn$ integers: the results.