Background

Problem Description

Little S does not like sets, does not like natural numbers, does not like summation, does not like products, does not like minimum values, does not like maximum values, and does not like $\operatorname{mex}$, so this problem exists.

Given $n, k$, find how many multisets of integers $S$ satisfy:

• $|S| = k$.
• For any $x \in S$, $0 \le x \le n$.
• $\displaystyle{\prod_{x \in S} x = \min_{x \in S} x}$.
• $\displaystyle{\sum_{x \in S} x = \min_{x \in S} x + \max_{x \in S} x + {\operatorname{mex}}(S)}$.

Note: $\bf{mex}$ is the smallest natural number that does not appear in the set.

Input Format

This problem contains multiple test cases.

The first line of input contains a positive integer $T$, which denotes the number of test cases.

For each test case, the input contains one line with two positive integers $n, k$.

Output Format

For each test case, output one line with one integer representing the answer.

7
1 4
2 4
5 3
2 100
3 8
20 50
499122178 4

1
2
0
3
5
39
998244353

Hint

Additional Notes.

To help contestants understand the statement better, here are several examples of valid/invalid sets:

• $\{0, 1, 2, 2\}$.

This set satisfies the requirements, because $0 \times 1 \times 2 \times 2 = 0 = \min\{0, 1, 2, 2\}$, and $0 + 1 + 2 + 2 = 5$, $\min\{0, 1, 2, 2\} + \max\{0, 1, 2, 2\} + \operatorname{mex}\{0, 1, 2, 2\} = 0 + 2 + 3 = 5$.

• $\{3, 5\}$.

This set does not satisfy the requirements, because although $3 + 5 = 8$, $\min\{3, 5\} + \max\{3, 5\} + \operatorname{mex}\{3, 5\} = 3 + 5 + 0 = 8$, we have $3 \times 5 \ne \min\{3, 5\}$.

• $\{1, 9, 1, 9, 8, 1, 0\}$.

This set does not satisfy the requirements, because although $1 \times 9 \times 1 \times 9 \times 8 \times 1 \times 0 = 0 = \min\{1, 9, 1, 9, 8, 1, 0\}$, its sum is $29$, not $\min + \max + \operatorname{mex} = 0 + 9 + 2 = 11$.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 10^6$, $1 \le n, k \le 10^{18}$.

Translated by ChatGPT 5