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 Nth row of pascal triangle starting with 0. Dukkar asks Pika to find how many numbers in nth 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?
Input
The first line of the test file will contain T (T < 100000) where T is the no. of test cases. Each of the next T lines will contain two integers N (0 <= N <= 10^{18}) and P (2 <= P <= 10^{5}) as defined above.
Output
For each test case print on each line K the number of numbers divisible by P on Nth row of the pascal triangle.
Example
Input: 2 2 2 7 7 Output: 1 6
hide comments
shantanu tripathi:
20150829 15:29:34
fun with lucas ...:) AC in one go.. 

:.Mohib.::
20150726 10:02:50
Good learning problem......!! 

Shubham Jain:
20150609 15:50:38
learned a new formula but trying for proof of that :) 

Aman Agarwal:
20150602 10:55:51
Nice problem..similar one HLP_RAMS Last edit: 20150608 17:37:55 

ASHUTOSH DWIVEDI:
20150520 16:30:28
awesome problem really enjoyed it............:) 

sj:
20140711 09:47:33
good problem


BLANKRK:
20140704 08:51:02
nice prob!!! 

fitcat:
20140313 12:20:39
Two entries in Row 13 are incorrect in the figure. They should be 286 instead of 186. BTW, nice problem.


Flago:
20140310 12:12:38
Nice one.


NISHANT RAJ:
20140310 07:18:03
@francky:here distribution of P doesn't do any thing in problem...

Added by:  NISHANT RAJ 
Date:  20140309 
Time limit:  0.100s0.800s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own 