「KDOI-04」Again Counting Set


小 S 不喜欢集合，不喜欢自然数，不喜欢求和，不喜欢求积，不喜欢最小值，不喜欢最大值，不喜欢 $\operatorname{mex}$，所以有了这题。 给出 $n,k$，求有多少个可重**整数**集合 $S$ 满足： * $|S|=k$； * 对于任意 $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)}$。 **注： $\bf{mex}$ 指集合中没有出现过的最小的自然数。**

**本题包含多组测试数据。** 输入的第一行包含一个正整数 $T$，表示测试数据组数。 对于每组测试数据，输入包含一行两个正整数 $n,k$。

对于每组测试数据，输出一行一个整数表示答案。

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

1
2
0
3
5
39
998244353

**【补充说明】** 为了更好的让选手理解题面，给出若干合法/不合法集合例子： + $\{0,1,2,2\}$。 该集合是一个符合要求的集合，因为 $0\times 1\times 2\times 2=0=\min\{0,1,2,2\}$，$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\}$ 该集合不是一个符合要求的集合，因为虽然 $3+5=8,\min\{3,5\}+\max\{3,5\}+\operatorname{mex}\{3,5\}=3+5+0=8$，但是 $3\times 5\not=\min\{3,5\}$。 + $\{1,9,1,9,8,1,0\}$。 该集合不是一个符合要求的集合，因为虽然 $1\times 9\times 1\times 9\times 8\times 1\times 0=0=\min\{1,9,1,9,8,1,0\}$，但是其和为 $29$ 而并非 $\min+\max+\operatorname{mex}=0+9+2=11$。 **【数据范围】** 对于 $100\%$ 的数据，保证 $1\le T\le10^6$，$1\le n,k\le10^{18}$。 |测试点编号|分值|$T\le$|$k\le$|$n$| |:-:|:-:|:-:|:-:|:-:| |$1$|$10$|$5$|$5$|$\le5$| |$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$|$\le10$| |$8$|$10$|$10^5$|$10^3$|$\le10^3$| |$9$|$10$|$10^6$|$10^{18}$|$\le10^{8}$| |$10$|$10$|$10^6$|$10^{18}$|$\le10^{18}$|