|
Марсианские факториалы 3
(Время: 0,25 сек. Память: 32 Мб Сложность: 91%)
В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно B×10E различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.
Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием B×10E. А символы в конце – это конечно же нули – ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули начиная с 5! = 1·2·3·4·5 = 120. А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 – так что у предположения профессора есть разумные основания!
Теперь ученым срочно нужна программа, которая по заданным числам N, B и E найдет количество нулей в конце записи в системе счисления с основанием B×10E числа N! = 1·2·3·…·(N-1)·N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!
Входные данные
Входной файл INPUT.TXT содержит натуральное число T – количество тестов. В следующих T строках содержится по три числа N, B и E, разделенные пробелом. (1 ≤ T ≤ 100,1 ≤ N ≤ 101000, 1 ≤ B ≤ 109, 0 ≤ E ≤ 109, B + E ≠ 1).
Выходные данные
В выходной файл OUTPUT.TXT выведите на каждый тест ответ на задачу с новой строки.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
100 10 0
5 1 1
43 2 1
3 1 2 | 24
1
9
0 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
