# Divisibility

**Problem Statement**

A combination is a way of selecting several things out of a larger group, where order does not matter.

^{n}C

_{k}represents number of ways of selecting k things out of n different thing. You are given a prime number p. Find out number of

^{n}C

_{k}'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 < 10
^{100} - p < 10
^{9}

**Sample Input**

```
```

2

3 3

7 5

**Sample Output**

```
```

2

2

**Explanation**

For first test case,out of

^{3}C

_{0}(1),

^{3}C

_{1}(3),

^{3}C

_{2}(3) &

^{3}C

_{3}(1),

^{3}C

_{1}&

^{3}C

_{2}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