Васина арифметика 2
После того, как Вася узнал на факультативе по программированию, что такое факториал, у него опять значительно возрос интерес к математике. Решив оставить после себя след в этой науке он придумал новую операцию – мультифакториал и теперь тщательно исследует её.
Для начала он ввёл понятие простого факториала. Согласно определению Васи, простой факториал заданного числа n – это произведение всех целых чисел больших нуля, записанных начиная с заданного числа n в убывающем порядке, каждый сомножитель которого на единицу меньше предыдущего.
Вполне логично, что Вася ввел понятие 2-факториала, 3-факториала и т.д. и вообще k-факториала, которые он объединил в одно определение – мультифакториал порядка k.
Мультифакториалом порядка k Вася назвал произведение всех целых чисел больших нуля, записанных начиная с заданного числа n в убывающем порядке, каждый сомножитель которого на k меньше предыдущего.
Вот формульные представления этих терминов, придуманные Васей:
n! = n ∙ (n-1) ∙ (n-2) ∙ (n-3)...
n!! = n ∙ (n-2) ∙ (n-4) ∙ (n-6)...
n!!! = n ∙ (n-3) ∙ (n-6) ∙ (n-9)...
В общем виде формулу Вася записал так:
Чтобы приблизить вновь созданный раздел математики к школьной жизни, Вася заинтересовался вопросом: сколько разных делителей имеет заданный мультифакториал порядка k?
Входные данные
Первая строка содержит количество примеров в задании N. Единственная строка каждого примера содержит запись заданного мультифакториала. Известно, что числовая часть в его записи не превышает 1000, а порядок k – не больше 20-ти. Известно также, что в одном тестовом примере нет двух одинаковых примеров.
Выходные данные
Для каждого тестового примера вывести в отдельной строке сначала его номер: Sample i: – где i – номер примера, а далее через пробел единственное число: количество делителей полученного значения мультфакториала порядка k. Если это количество превышает 10^18 Вася просит вывести придуманный им же символ бесконечности oo.