시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 112 89 67 74.444%

문제

알고리즘 기말고사는 용어와 정의를 선으로 연결하는 문제만 나온다. 왼쪽에는 용어 N개, 오른쪽에는 정의 N개가 한 줄로 나열되어 있다. 학생들은 각 용어에 해당하는 정의를 선으로 그려야 한다.

선영이는 자신의 뛰어난 프로그래밍 실력을 믿고 공부를 하지 않았다. 하지만, 기말고사는 프로그래밍 실력과 관계없는 문제만 나왔다. 따라서, 선영이는 문제를 모두 찍으려고 한다.

S(N,k)를 선영이가 문제를 모두 풀었을 때, 적어도 위에서부터 처음 k개 용어는 반드시 틀리는 경우의 수라고 하자.

N과 k가 주어졌을 때, S(N,k)를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 테스트 케이스 번호와 두 정수 N과 k가 주어진다. (1 ≤ N ≤ 17, 0 ≤ k ≤ N)

출력

각 테스트 케이스 마다 테스트 케이스 번호와 S(N,k)를 출력한다.

예제 입력

4
1 4 1
2 7 3
3 10 5
4 17 17

예제 출력

1 18
2 3216
3 2170680
4 130850092279664

힌트