SPOJ.com - Problem DUKKAR

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?

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¹⁸) and P (2 ≤ P ≤ 10⁵) 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

Submit solution!

hide comments

< Previous 1 2 Next >

	shantanu tripathi: 2015-08-29 15:29:34 fun with lucas ...:) AC in one go..
	:.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)
	NISHANT RAJ: 2014-03-10 07:18:03 @francky:here distribution of P doesn't do any thing in problem... I will check time limit for other programing lang... and i have increased time limit to 0.8 sec for python users --ans(Francky)--> For distribution of prime, it's very important if you want to make a faster solution. Some other method can be faster with small primes... I'll try a C edition and a Python one, I hope they will pass. Edit : they pass, but with fast IO I got TLE, I suspect input contains trailing spaces or other bad formatting, is it a purpose or an error ? Maybe rather the end of one file isn't finished by '\n'. (It was that!!!) But thanks for having let more time for slow languages. @francky :yes input file doesn't contain "\n" Last edit: 2014-03-10 12:47:59

Submit solution!

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