P9034 "KDOI-04" Again Counting Set.


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

**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$.

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

**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}$. | Test Point ID | Score | $T \le$ | $k \le$ | $n$ | | :-: | :-: | :-: | :-: | :-: | | $1$ | $10$ | $5$ | $5$ | $\le 5$ | | $2$ | $10$ | $10^5$ | $10^{18}$ | $= 1$ | | $3$ | $10$ | $10^5$ | $10^{18}$ | $= 2$ | | $4$ | $10$ | $10^5$ | $10^{18}$ | $= 3$ | | $5$ | $10$ | $10^5$ | $10^{18}$ | $= 4$ | | $6$ | $10$ | $10^5$ | $10^{18}$ | $= 5$ | | $7$ | $10$ | $10^5$ | $10$ | $\le 10$ | | $8$ | $10$ | $10^5$ | $10^3$ | $\le 10^3$ | | $9$ | $10$ | $10^6$ | $10^{18}$ | $\le 10^{8}$ | | $10$ | $10$ | $10^6$ | $10^{18}$ | $\le 10^{18}$ | Translated by ChatGPT 5