带余除法

题目描述

我们已经学过带余除法。对于两个正整数 $n,q$，如果 $n$ 除以 $q$ 的商为 $k$，余数为 $r$，我们可以写出带余除法算式 $n\div q = k \cdots\cdots r$，或被记为 $n\div q = k (\text{r. } r)$。本题中，为了简化，哪怕 $r=0$，我们也要写出这个余数。

现在有一个带余除法，然而你只知道被除数 $n​$ 和商 $k​$，而并不知道除数 $q​$ 和余数 $r​$。你想知道余数有多少种可能。

输入格式

本题有多组测试数据。输入的第一行有一个正整数 $T$，表示数据组数。

之后 $T$ 行，每行有一个正整数 $n$ 和自然数 $k$，分别表示带余除法的被除数和商。

输出格式

对于每组测试数据，输出一行一个自然数，表示余数的不同可能性数量。

样例 #1

样例输入 #1

2
10 2
1 0

样例输出 #1

2
1

样例 #2

样例输入 #2

参见 division/division2.in

样例输出 #2

参见 division/division2.ans

提示

【样例 1 解释】

对于第一组数据，被除数为 $10$，商为 $2$。

• 如果除数是 $1,2,3$，那么商分别是 $k=10,5,3$，不符合题意。
• 如果除数是 $4$，那么商为 $2$，余数为 $r=2$。
• 如果除数是 $5$，那么商为 $2$，余数为 $r=0$。
• 如果除数是 $6,7,8,9,10$，那么商都是 $1$，不符合题意。
• 如果除数 $>10$，那么商为 $0$，不符合题意。

对于第二组数据，被除数为 $1$，商为 $0$。

只要除数 $q>1$，那么 $1\div q = 0 \cdots\cdots 1$ 一定是正确的带余除法算式。余数只有 $1$ 这一种可能。

【数据范围】

对于前 $30\%$ 的数据，保证 $1\le n\le 1000$，$0\le k\le 1000$。

另有 $20\%$ 的数据，保证 $k\le 10^5$。

另有 $20\%$ 的数据，保证 $k\ge 10^9$。

对于全体数据，保证 $1\le T\le 10$，$1\le n\le 10^{14}$，$0\le k\le 10^{14}$。

附件：division.zip