题目背景

题目描述

小 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$		$\le5$
$2$		$10^5$	$10^{18}$	$=1$
$3$				$=2$
$4$				$=3$
$5$				$=4$
$6$				$=5$
$7$			$10$	$\le10$
$8$			$10^3$	$\le10^3$
$9$		$10^6$	$10^{18}$	$\le10^{8}$
$10$				$\le10^{18}$