시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 366 187 129 51.807%

문제

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

예를 들어, n=24, k=3일 때, 2가지로 나타낼 수 있다. {2, 3, 19}, {2, 5, 17} 합이 24가 되는 서로 다른 소수 3개는 이 2가지를 제외하고는 없다. 또, n=24, k=2일 때 답은 {5, 19}, {7, 17}, {11, 13} 3가지이며, n=2, k=1일 때 답은 {2} 1가지이다. n=1, k=1일 경우에는 1은 소수가 아니기 때문에 답은 0이다. 마지막으로 서로 다른 2개 소수의 합이 4가 되는 경우도 없기 때문에, n=4, k=2도 답이 0이다.

입력

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

출력

각 테스트 케이스에 해당하는 경우의 수를 한 줄에 하나씩 출력한다. 정답은 항상 231보다 작다.

예제 입력 1

12
24 3
24 2
2 1
1 1
4 2
18 3
17 1
17 3
17 4
100 5
1000 10
1120 14

예제 출력 1

2
3
1
0
0
2
1
0
1
55
200102899
2079324314
W3sicHJvYmxlbV9pZCI6IjM5MDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWQ1NjkiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMThjXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzIxOCBuXHVhY2ZjIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Yywgblx1Yzc0NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IGtcdWFjMWNcdWM3NTggXHVjMThjXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1YjM2N1x1YzE0OFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5Y2MgXHViMmU0XHViOTc4IFx1YWNiZFx1YzZiMCgzKzUsIDUrMylcdWIyOTQgXHViYWE4XHViNDUwIDFcdWFjMDBcdWM5YzBcdWI4NWMgXHVjMTNjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBuPTI0LCBrPTNcdWM3N2MgXHViNTRjLCAyXHVhYzAwXHVjOWMwXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiB7MiwgMywgMTl9LCB7MiwgNSwgMTd9IFx1ZDU2OVx1Yzc3NCAyNFx1YWMwMCBcdWI0MThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMxOGNcdWMyMTggM1x1YWMxY1x1YjI5NCBcdWM3NzQgMlx1YWMwMFx1YzljMFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NThcdWFjZTBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWI2MTAsIG49MjQsIGs9Mlx1Yzc3YyBcdWI1NGMgXHViMmY1XHVjNzQwIHs1LCAxOX0sIHs3LCAxN30sIHsxMSwgMTN9IDNcdWFjMDBcdWM5YzBcdWM3NzRcdWJhNzAsIG49Miwgaz0xXHVjNzdjIFx1YjU0YyBcdWIyZjVcdWM3NDAgezJ9IDFcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIG49MSwgaz0xXHVjNzdjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAxXHVjNzQwIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM1NDRcdWIyYzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjJmNVx1Yzc0MCAwXHVjNzc0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCAyXHVhYzFjIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgNFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIG49NCwgaz0yXHViM2M0IFx1YjJmNVx1Yzc3NCAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBuXHVhY2ZjIGtcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIChuICZsZTsgMTEyMCwgayAmbGU7IDE0KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzQwIFx1ZDU2ZFx1YzBjMSAyPHN1cD4zMTxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5MDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdW0gb2YgRGlmZmVyZW50IFByaW1lcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBwb3NpdGl2ZSBpbnRlZ2VyIG1heSBiZSBleHByZXNzZWQgYXMgYSBzdW0gb2YgZGlmZmVyZW50IHByaW1lIG51bWJlcnMgKHByaW1lcyksIGluIG9uZSB3YXkgb3IgYW5vdGhlci4gR2l2ZW4gdHdvIHBvc2l0aXZlIGludGVnZXJzIG4gYW5kIGssIHlvdSBzaG91bGQgY291bnQgdGhlIG51bWJlciBvZiB3YXlzIHRvIGV4cHJlc3MgbiBhcyBhIHN1bSBvZiBrIGRpZmZlcmVudCBwcmltZXMuIEhlcmUsIHR3byB3YXlzIGFyZSBjb25zaWRlcmVkIHRvIGJlIHRoZSBzYW1lIGlmIHRoZXkgc3VtIHVwIHRoZSBzYW1lIHNldCBvZiB0aGUgcHJpbWVzLiBGb3IgZXhhbXBsZSwgOCBjYW4gYmUgZXhwcmVzc2VkIGFzIDMgKyA1IGFuZCA1ICsgMyBidXQgdGhleSBhcmUgbm90IGRpc3Rpbmd1aXNoZWQuPFwvcD5cclxuXHJcbjxwPldoZW4gbiBhbmQgayBhcmUgMjQgYW5kIDMgcmVzcGVjdGl2ZWx5LCB0aGUgYW5zd2VyIGlzIHR3byBiZWNhdXNlIHRoZXJlIGFyZSB0d28gc2V0cyB7MiwgMywgMTl9IGFuZCB7MiwgNSwgMTd9IHdob3NlIHN1bXMgYXJlIGVxdWFsIHRvIDI0LiBUaGVyZSBhcmUgbm8gb3RoZXIgc2V0cyBvZiB0aHJlZSBwcmltZXMgdGhhdCBzdW0gdXAgdG8gMjQuIEZvciBuID0gMjQgYW5kIGsgPSAyLCB0aGUgYW5zd2VyIGlzIHRocmVlLCBiZWNhdXNlIHRoZXJlIGFyZSB0aHJlZSBzZXRzIHs1LCAxOX0sIHs3LCAxN30gYW5kIHsxMSwgMTN9LiBGb3IgbiA9IDIgYW5kIGsgPSAxLCB0aGUgYW5zd2VyIGlzIG9uZSwgYmVjYXVzZSB0aGVyZSBpcyBvbmx5IG9uZSBzZXQgezJ9IHdob3NlIHN1bSBpcyAyLiBGb3IgbiA9IDEgYW5kIGsgPSAxLCB0aGUgYW5zd2VyIGlzIHplcm8uIEFzIDEgaXMgbm90IGEgcHJpbWUsIHlvdSBzaG91bGRuJiMzOTt0IGNvdW50IHsxfS4gRm9yIG4gPSA0IGFuZCBrID0gMiwgdGhlIGFuc3dlciBpcyB6ZXJvLCBiZWNhdXNlIHRoZXJlIGFyZSBubyBzZXRzIG9mIHR3byBkaWZmZXJlbnQgcHJpbWVzIHdob3NlIHN1bXMgYXJlIDQuPFwvcD5cclxuXHJcbjxwPllvdXIgam9iIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHJlcG9ydHMgdGhlIG51bWJlciBvZiBzdWNoIHdheXMgZm9yIHRoZSBnaXZlbiBuIGFuZCBrLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgZGF0YXNldHMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9zIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBBIGRhdGFzZXQgaXMgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHBvc2l0aXZlIGludGVnZXJzIG4gYW5kIGsgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFlvdSBtYXkgYXNzdW1lIHRoYXQgbiAmbGU7IDExMjAgYW5kIGsgJmxlOyAxNDxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBiZSBjb21wb3NlZCBvZiBsaW5lcywgZWFjaCBjb3JyZXNwb25kaW5nIHRvIGFuIGlucHV0IGRhdGFzZXQuIEFuIG91dHB1dCBsaW5lIHNob3VsZCBjb250YWluIG9uZSBub24tbmVnYXRpdmUgaW50ZWdlciBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2Ygd2F5cyBmb3IgbiBhbmQgayBzcGVjaWZpZWQgaW4gdGhlIGNvcnJlc3BvbmRpbmcgZGF0YXNldC4gWW91IG1heSBhc3N1bWUgdGhhdCBpdCBpcyBsZXNzIHRoYW4gMjxzdXA+MzE8XC9zdXA+LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=