SP18917 DUKKAR - Dukkar and Pikka

Pika and Dukkar are roomie. Pika is a nerd and likes to play with mathematics! Pika's favourite topic is pascal triangle and he proclaims that he can solve any problem related to this. So Dukkar decides if it's really true! Dukkar gives a number $N$ and a prime number $P$. $N$ is the $N$th row of pascal triangle starting with $0$. Dukkar asks Pika to find how many numbers in $n$th row are divisible by $P$. Since the number can be very large so, Pika has to write a program. Since end sem are coming and Pika has to top in his batch so he asks you for help. Can you help Pika? 

The first line of the test file will contain $T\ (T\lt100000)$, where $T$ is the number of test cases. Each of the next $T$ lines will contain two integers $N\ (0\le N\le10^{18})$ and $P\ (2\le P\le 10^5)$ as defined above.

For each test case print on each line $K$ the number of numbers divisible by $P$ on $N$th row of the pascal triangle.