A combination is a way of selecting several things out of a larger group, where order does not matter. nCk represents number of ways of selecting k things out of n different thing. You are given a prime number p. Find out number of nCk's (0<=k<=n) that are completely divisible by given prime number.
First line of input contains T (number of test cases).
Each of the next T line contains two space separated number n and p.
For each test case, print required result in a separate line.
- T <= 100
- n < 10100
- p < 109
For first test case,out of 3C0 (1), 3C1 (3), 3C2 (3) & 3C3 (1),
3C1 & 3C2 are divisible by prime number 3. So the result is 2.
Problem Setter:Abhishek Sanghai