题目描述

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

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

输入格式

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

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

输出格式

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

样例

2
10 2
1 0

2
1

10
447 0
22 1
21 1
23 1
319 11
318 11
320 11
493 29
492 29
494 29

1
11
11
12
3
2
3
1
0
1

提示

【样例 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÷q=0⋯⋯1 一定是正确的带余除法算式。余数只有 1 这一种可能。

【数据范围】

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

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

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