问题 S: 求组合数 III
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：132
通过：60
题目描述
给定 n 组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出 
的值。
的值。输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a,b,p。
输出格式
共 n 行，每行输出一个询问的解。
输入样例 复制
3
5 3 7
3 1 5
6 4 13输出样例 复制
3
3
2数据范围与提示
1 ≤ n ≤ 20,
1 ≤ b ≤ a ≤ 1018,
1 ≤ p ≤ 105,
1 ≤ b ≤ a ≤ 1018,
1 ≤ p ≤ 105,