FACTBASE - Count Zero

no tags 

Count the zero at the end of N! when represented in base b.

Input

the first line is the number T (1 <= T <= 10^5) 

the Ith line in the T line contains two positive integers N (1 <= N <= 10^18), b (2 <= b <= 10^6)

Output

Consists of T lines, the Ith line is the result of the test i

Example

Input:
6
3 7
5 2
10 3
10 9
1000 2
1000 30

Output:
0
3
4
2
994
249

hide comments
:C++:: 2013-02-06 17:46:57

Are all numbers fit in long long in c/c++
Whats the error in my code now...
I think it should pass now within time...
Why 45...

Last edit: 2013-02-06 18:37:49
Francky: 2013-02-06 13:45:33

@:C++: You got TLE or WA on 8/10 of input files. So a score of 20%.
Edit : With given constraints, one can prove that answer is bounded by ***, so we can know in advance the suited container structure.

Last edit: 2013-02-06 18:22:38
:C++:: 2013-02-06 13:16:52

What does score 20 mean....
Is it that only my program is giving correct output for only 20% cases???

Spar!k: 2013-02-03 22:54:23

Last edit: 2013-04-26 02:07:38
Francky: 2013-02-03 20:13:27

I still think this one belongs to classical, and need better judge.
Impatient for harder cases will enjoy http://www.spoj.com/problems/FCTRHELL/
Tonight we dine in hell!

Francky: 2013-01-28 17:26:27

We should waiting for something like a week, read others opinion, and hope return to classical with default judge (and rejudge). If nothing is done within a week, we'll can consider a harder edition. Any other suggestions ?

(Tjandra Satria Gunawan)(曾毅昆): 2013-01-28 16:11:28

I agree with Francky, but the judge seems still crash (sometimes get 0k mem and 0 pts) so if change the scoring to binary, it will accept all submissions, so my suggestion is create new problem like this (with default judge)..

Last edit: 2013-01-28 16:11:41
Francky: 2013-01-27 22:28:06

I made a terrible mistake in considering this one as a simple variant of FCTRL. It's not and I must apologize for my first (deleted) comments where I suggested it was tutorial, now I think it belongs to classical. Not so hard, but classical. Thanks for this problem. Sorry again for my first comment.
Edit : scoring should perhaps stay at binary, any other opinion ?

Last edit: 2013-01-27 22:39:07
Francky: 2013-01-27 20:46:16

OK, It's true !

(Tjandra Satria Gunawan)(曾毅昆): 2013-01-27 20:32:52

@Francky: No, the example is correct (based on my program, My output match the example given)..


Added by:Lê Tiến Khoa
Date:2013-01-15
Time limit:0.200s-1.399s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64