1994-1995 ACM International Collegiate Programming Contest
Western European Regional
Practice Session

Problem E


Most people participating in the ACM scholastic programming contest have at some stage been asked: 'Can you give an example of the type of problems you have to solve there?'. The most common example selected in response is the 8-queens problem.

Of course, all of you have at one time or the other programmed the 8-queens problem. So here is a small variation on that theme: determine the number of ways you can place R rooks on an R R chess board, such that no two rooks are on the same file or on the same rank.

Input Specification

The first line of input contains an integer N, specifying the number of test cases. Each of the N test cases consists of a single positive integer R (1 <= R <= 12) on a line by itself, indicating which R-rooks problem you have to solve.

Output Specification

For each test case, output the line 'There are S solutions to the R-rooks problem.', where S is the number of solutions, and R is the size of the problem.

Example Input


Example Output

There are 1 solutions to the 1-rooks problem.
There are 2 solutions to the 2-rooks problem.
There are 24 solutions to the 4-rooks problem.