Problem

Given 2 integers, N and k, the task is to find the number of groups of size k, whose elements are positive integers and add up to N.

Two groups are considered distinct if they have a different representation when their elements are sorted in ascending order.

Example

For N = 8 and k = 4, the valid groups are:

• {1, 1, 1, 5}
• {1, 1, 2, 4}
• {1, 1, 3, 3}
• {1, 2, 2, 3}
• {2, 2, 2, 2} Therefore, the expected output is 5.

Note

The order of elements does not matter. For example, the groups {1, 1, 1, 5}, {1, 1, 5, 1}, {1, 5, 1, 1}, and {5, 1, 1, 1} are all considered the same because their sorted representation is {1, 1, 1, 5}.

Input Format

• The first line of input is an integer T, representing the number of test cases.
• The following T lines each contain two space-separated integers, N and k.

Output Format

• Output T lines, where each line contains the solution for the corresponding test case.