SP13977 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.

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.

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.