문제2713--Faculty Dividing Powers

### 2713: Faculty Dividing Powers

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 9  통과: 1
[제출] [채점기록] [묻고답하기]

#### 문제 설명

Fred Faculty and Paul Power love big numbers. Day after day Fred chooses a random integer n and he computes n!. His friend Paul amuses himself by computing several powers of his randomly chosen integer k like k2, k3, ... and so on. On a hot summer day, Fred and Paul got really, really bored, so they decided to play a joke on their buddy Dave Divider. Fred chooses a random integer n while Paul chooses a random integer k. They want Dave to find the biggest integer i such that $k^i$ divides n! without a remainder, otherwise they will throw a cake in Dave's face. Because Dave does not like cakes in his face, he wants you to help him finding that integer i.

#### 입력 설명

The first line contains the number of test cases t (1 ≤ T ≤ 100). Each of the following t lines contains the two numbers n, k (2 ≤ n ≤ 1018, 2 ≤  k ≤ 1012) separated by one space.

#### 출력 설명

For each test case, print the maximum integer i on a separate line.

#### 입력 예시 Copy

2
5 2
10 10

#### 출력 예시 Copy

3
2