Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P194PROG - Problem G - Chuyện chữ số 0 tận cùng

Cho hai số nguyên dương n và b được viết ở hệ thập phân, hãy cho biết số n! viết ở hệ đếm cơ số b sẽ có bao nhiêu chữ số 0 tận cùng.

Input

Dòng đầu tiên chứa 1 số nguyên T là số bộ test (1 ≤ T ≤ 10).

Mỗi bộ test sẽ có dạng như sau: dòng duy nhất của input chứa 2 số nguyên n và b (1 ≤ n ≤ 1018, 2 ≤ b ≤ 1012).

Output

Với mỗi bộ test, in ra trên một dòng một số nguyên duy nhất là kết quả của bài toán.

Example

Input
5
6 9
38 11
5 2
5 10
5 100

Output
1
3
3
1
0

Cho hai số nguyên dương n và b được viết ở hệ thập phân, hãy cho biết số n! viết ở hệ đếm cơ số b sẽ có bao nhiêu chữ số 0 tận cùng.


Được gửi lên bởi:adm
Ngày:2019-03-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.