Васина арифметика 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.