서로 다른 소수의 합

양의 정수는 서로 다른 소수의 합으로 나타낼 수 있다. 두 정수 $n$과 $k$가 주어졌을 때, $n$을 서로 다른 $k$개의 소수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서만 다른 경우(예: $3+5$와 $5+3$)는 같은 방법으로 보고 한 가지로 센다.

예를 들어 $n=24$, $k=3$이면 방법은 $\{2, 3, 19\}$와 $\{2, 5, 17\}$의 2가지이다. $n=24$, $k=2$이면 $\{5, 19\}$, $\{7, 17\}$, $\{11, 13\}$의 3가지이다. $n=2$, $k=1$이면 $\{2\}$의 1가지이다. $n=1$, $k=1$이면 1은 소수가 아니므로 답은 0이다. 또한 서로 다른 두 소수의 합이 4가 되는 경우는 없으므로 $n=4$, $k=2$의 답도 0이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄에 두 정수 $n$과 $k$가 공백으로 구분되어 주어진다. ($n \le 1120$, $k \le 14$)

각 테스트 케이스마다 방법의 수를 한 줄에 하나씩 출력한다. 정답은 항상 $2^{31}$보다 작다.