TMB  Thousands ByteMan March
Leo invited all his friends to a giant meeting for peace in byteland.
All people came in bus which were all full.
Last year, they were only 4 people : A, B, C, D.
As Leo likes structured things, he thought to form groups.
All the ways to form homogeneous teams were :
{{A,B,C,D}} : one team of 4 (one way), {{A}, {B}, {C}, {D}} : four 'teams' of 1 (one way more), {{A,B}, {C,D}} or {{A,C}, {B,D}} or {{A,D}, {B,C}} : two teams of 2 (3 ways more).
for a total of 5 ways. But this year many people are awaited.
Input
The input begins with the number T of test cases in a single line.
In each of the next T lines there are two integers : N, K.
N is the quantity of bus that came to the meeting.
K is the common capacity of each bus.
Output
For each test case, your task is to calculate the number of ways people
can form homogeneous teams.
The answer can be a big number and could not fit in a 64bit container.
Example
Input: 3 2 2 1 6 2 3 Output: 5 27 27
Explanations
With lower letters, here are 27 ways for 2×3 people.
{{a,c,e},{b,d,f}},{{a,c,d},{b,e,f}},{{a,b},{c,e},{d,f}},{{a,f},{b,e},{c,d}}, {{a,b,f},{c,d,e}},{{a,c},{b,f},{d,e}},{{a,e},{b,f},{c,d}},{{a,b},{c,d},{e,f}}, {{a,e},{b,d},{c,f}},{{a,e,f},{b,c,d}},{{a,b,e},{c,d,f}},{{a,d,e},{b,c,f}}, {{a,d},{b,e},{c,f}},{{a,d},{b,c},{e,f}},{{a,d},{b,f},{c,e}}, {{a,c,f},{b,d,e}},{{a,b,c},{d,e,f}},{{a},{b},{c},{d},{e},{f}}, {{a,b,c,d,e,f}},{{a,c},{b,d},{e,f}},{{a,c},{b,e},{d,f}},{{a,b},{c,f},{d,e}}, {{a,f},{b,d},{c,e}},{{a,f},{b,c},{d,e}},{{a,e},{b,c},{d,f}}, {{a,d,f},{b,c,e}},{{a,b,d},{c,e,f}}
Constraints
0 < T ≤ 100 0 < K ≤ 100 0 < N ≤ 100
Uniformrandom input in the range. Basic 1/6kB Python code can get AC under 1.5s, around 0.18s using PIKE (quite my first PIKE code), (timings edited 20170211 after compiler changes).
hide comments
nadstratosfer:
20181023 21:03:44
Amazing one. As usual with Francky's problems, the concept alone is not trivial, but once figured out, still have to reduce. Feels fantastic to get AC, or rather not to get WA, as to be honest I've been getting lost on my way to the solution. Writing this was like listening to wife when stoned, you fully comprehend every word she's saying, but by the end of the sentence, you don't remember how it all began ;)


Apoorv Jindal:
20131218 20:56:42
@Francky Good problem!How can I optimize my python 2.7 code? Any suggestions?

Added by:  Francky 
Date:  20130303 
Time limit:  2.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 