Problem Statement

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.

Input

First line of input contains T (number of test cases).
Each of the next T line contains two space separated number n and p.

Output

For each test case, print required result in a separate line.

Constraints
• T <= 100
• n < 10100
• p < 109

Sample Input

``` 2 3 3 7 5 ```

Sample Output

``` 2 2 ```

Explanation

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

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 1 Second(s)
Score: 75 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0