TMB - Thousands ByteMan March

no tags 

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

Uniform-random 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 2017-02-11 after compiler changes).


hide comments
nadstratosfer: 2018-10-23 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 ;)

Just noticed I've got a pretty good time, which is surprising as it feels there's still a lot to optimize. Will enjoy spending some more time looking into this beauty. Thanks!

=(Francky)=> Congrats, and thanks for your appreciation ;-)

Last edit: 2018-10-24 00:47:23
Apoorv Jindal: 2013-12-18 20:56:42

@Francky Good problem!How can I optimize my python 2.7 code? Any suggestions?
--ans(francky)--> It's always a good idea to try to sieve something, but the code will be harder to write. Yet a nice job.
Edit(apoorv)--> Thanks for replying, i'll think about it.

Last edit: 2013-12-19 15:24:54

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