该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

自举办完最强大脑比拼以后，大维受到了打击：大家怎么都这么厉害！于是大维决定发愤图强，他要把新华字典背下来！他买了一本《超级豪华无敌加强plus版新华字典》，一共有 $n$ 页，大维决定用 $m$ 天时间把它全部背下来！

题目描述

作为一个规划性超强的人，大维决定规划两个数字 $a,b$，其中 $a,b$ 均为非负整数。
第 1 天背 $a$ 页，第 2 天背 $a+b$ 页，第三天背 $a+2b$ 页……第 $m$ 天背 $a+(m-1)b$ 页。

大维想知道，有多少种学习计划可以让他在第 $m$ 天刚好背完整本书，不多也不少？

输入格式

输入第一行包含一个整数 $T$，表示有 $T$ 组测试数据。
接下来每组测试数据包含两个整数 $n,m$，表示新华字典的页数和天数。

输出格式

对于每组测试数据，输出有多少种方案。

样例

3
6 2
3 4
6 3

4
0
3

样例解释

当 $n=6,m=2$ 时，每天读书的方案为：
0 6
1 5
2 4
3 3

当 $n=3,m=4$ 时，无法设计出读书方案。

当 $n=6,m=3$ 时，每天读书的方案为：
0 2 4
1 2 3
2 2 2

数据范围

测试点编号 | 数据范围
1∼2 | $T=100,\ n\le10^5,\ m=1$
3∼4 | $T=100,\ n\le10^7,\ m\bmod2=1,\ n\bmod m\neq0$
5∼6 | $T=10,\ n\le1000,\ m\le20$
7∼10 | $T\le10^6,\ n,m\le10^9$