All Submissions


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

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

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