Algorithm Final Exam

The algorithm final exam asks for one thing only, connecting terms to definitions with lines. The left column lists $N$ terms and the right column lists $N$ definitions, each in a single row, and a student draws one line from every term to a definition. Two different terms go to two different definitions, so one answer sheet is a permutation that maps terms to definitions.

Seonyeong trusted her programming skill and did not study. The exam had nothing to do with programming, so she guesses every line.

Let $S(N,k)$ be the number of answer sheets in which the first $k$ terms from the top are all wrong once Seonyeong has drawn every line. The remaining $N-k$ terms may be right or wrong.

Given $N$ and $k$, write a program that computes $S(N,k)$.

The first line contains the number of test cases. Each test case is one line holding the test case number and two integers $N$ and $k$, separated by spaces. ($1 \le N \le 17$, $0 \le k \le N$)

For each test case, print the test case number given in the input and $S(N,k)$ on one line, separated by a single space.