Consider a chessboard with *n* rows and *n* columns.
In how many ways can we place *n* rooks
so that at least two rooks threaten each other?

For instance,
these are two of the ways for *n* = 6:

showmover=false,
label=false,
maxfield=f6,
setpieces=rd6,ra5,rf3,rc3,rb2,re1
showmover=false,
label=false,
maxfield=f6,
setpieces=re6,re2,re3,rb4,rb3,ra3

**Input**

Input consists of several numbers 1≤ *n*≤ 6.
A special case with *n* = 0 marks the end of input.

**Output**

For every *n*, print the number of different ways
to place *n* rooks on a chessboard *n* × *n*
so that at least two rooks threaten each other.
For every 1≤ *n*≤ 6, this number has less than 10 digits.

Public test cases

**Input**

2 3 0

**Output**

4 78