说明

自举办完最强大脑比拼以后，蒟蒻队长受到了打击，怎么大家都这么厉害！

于是蒟蒻队长决定发愤图强，他要把新华字典背下来！

他买了一本《超级豪华无敌加强plus版新华字典》，一共有 $n$ 页，蒟蒻队长决定用 $m$ 天时间把它全部背下来！

作为一个规划性超强的人，蒟蒻队长决定规划一个学习计划，他决定规划两个数字 $a,b$

第一天背 $a$ 页，第二天背 $a+b$ 页，第三天背 $a+2 * b$ 页 ...... 第 $m$ 天背 $a + (m - 1) * b$ 页

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

输入格式

题目采用多组测试数据

输入第一行包含一个整数 $T$ 表示有 $T$ 组测试数据

对于每组测试数据，输入两个整数 $n,m$ 表示新华字典的页数和天数

测试点编号	数据范围
$1 \sim 2$	$T=100,n \leq 10^5,m=1$
$3 \sim 4$	$T=100,n \leq 10^7,m%2=1,n%m!=0$
$5 \sim 6$	$T=10, n \leq 1000, m \leq 20$
$5 \sim 10$	$T \leq 10^6, n,m \leq 10^9$

</span>

输出格式

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

3
100 5
233 10
999 9

11
0
28

来源

CSP模拟赛