{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/s502kfip.png)"},{"iden":"statement","content":"小 S 不喜欢集合，不喜欢自然数，不喜欢求和，不喜欢求积，不喜欢最小值，不喜欢最大值，不喜欢 $\\operatorname{mex}$，所以有了这题。\n\n给出 $n,k$，求有多少个可重**整数**集合 $S$ 满足：\n\n* $|S|=k$；\n* 对于任意 $x\\in S$，$0\\le x\\le n$；\n* $\\displaystyle{\\prod_{x\\in S} x=\\min_{x\\in S} x}$；\n* $\\displaystyle{\\sum_{x\\in S} x=\\min_{x\\in S} x+\\max_{x\\in S}x+{\\operatorname{mex}}(S)}$。\n\n**注： $\\bf{mex}$ 指集合中没有出现过的最小的自然数。**"},{"iden":"input","content":"**本题包含多组测试数据。**\n\n输入的第一行包含一个正整数 $T$，表示测试数据组数。\n\n对于每组测试数据，输入包含一行两个正整数 $n,k$。"},{"iden":"output","content":"对于每组测试数据，输出一行一个整数表示答案。"},{"iden":"note","content":"**【补充说明】**\n\n为了更好的让选手理解题面，给出若干合法/不合法集合例子：\n\n+ $\\{0,1,2,2\\}$。\n\n该集合是一个符合要求的集合，因为 $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$。\n\n+ $\\{3,5\\}$\n\n该集合不是一个符合要求的集合，因为虽然 $3+5=8,\\min\\{3,5\\}+\\max\\{3,5\\}+\\operatorname{mex}\\{3,5\\}=3+5+0=8$，但是 $3\\times 5\\not=\\min\\{3,5\\}$。\n\n+ $\\{1,9,1,9,8,1,0\\}$。\n\n该集合不是一个符合要求的集合，因为虽然 $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$。\n\n**【数据范围】**  \n\n对于 $100\\%$ 的数据，保证 $1\\le T\\le10^6$，$1\\le n,k\\le10^{18}$。\n\n|测试点编号|分值|$T\\le$|$k\\le$|$n$|\n|:-:|:-:|:-:|:-:|:-:|\n|$1$|$10$|$5$|$5$|$\\le5$|\n|$2$|$10$|$10^5$|$10^{18}$|$=1$|\n|$3$|$10$|$10^5$|$10^{18}$|$=2$|\n|$4$|$10$|$10^5$|$10^{18}$|$=3$|\n|$5$|$10$|$10^5$|$10^{18}$|$=4$|\n|$6$|$10$|$10^5$|$10^{18}$|$=5$|\n|$7$|$10$|$10^5$|$10$|$\\le10$|\n|$8$|$10$|$10^5$|$10^3$|$\\le10^3$|\n|$9$|$10$|$10^6$|$10^{18}$|$\\le10^{8}$|\n|$10$|$10$|$10^6$|$10^{18}$|$\\le10^{18}$|"}],"translated_statement":null,"sample_group":[["7\n1 4\n2 4\n5 3\n2 100\n3 8\n20 50\n499122178 4","1\n2\n0\n3\n5\n39\n998244353\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}