DUKKAR - Dukkar and Pikka

no tags 

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?

pascal triangle

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 <= 1018)  and P (2 <= P <= 105) 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: 2015-08-29 15:29:34

fun with lucas ...:) AC in one go..

anuveshkothari: 2015-08-02 19:52:41

Last edit: 2015-08-02 19:52:58
:.Mohib.:: 2015-07-26 10:02:50

Good learning problem......!!

Shubham Jain: 2015-06-09 15:50:38

learned a new formula but trying for proof of that :)

Aman Agarwal: 2015-06-02 10:55:51

Nice problem..similar one HLP_RAMS

Last edit: 2015-06-08 17:37:55
ASHUTOSH DWIVEDI: 2015-05-20 16:30:28

awesome problem really enjoyed it............:)

sj: 2014-07-11 09:47:33

good problem
little bit of logic

BLANKRK: 2014-07-04 08:51:02

nice prob!!!

fitcat: 2014-03-13 12:20:39

Two entries in Row 13 are incorrect in the figure. They should be 286 instead of 186. BTW, nice problem.
@fitcat : yes fig is not up to correct.

Last edit: 2014-03-13 13:21:46
Flago: 2014-03-10 12:12:38

Nice one.

(Trying to submit C++ script under PHP tag give you WA... who would have guess :D)


Added by:NISHANT RAJ
Date:2014-03-09
Time limit:0.100s-0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own