После того, как Вася узнал на факультативе по программированию, что такое факториал, у него опять значительно возрос интерес к математике. Решив оставить после себя след в этой науке он придумал новую операцию -- мультифакториал и теперь тщательно исследует её. Для начала он ввёл понятие простого факториала. Согласно определению Васи, \textit{простой факториал} заданного числа \textbf{n} -- это произведение всех целых чисел больших нуля, записанных начиная с заданного числа \textbf{n} в убывающем порядке, каждый сомножитель которого на единицу меньше предыдущего. Вполне логично, что Вася ввел понятие \textbf{2}-факториала, \textbf{3}-факториала и т.д. и вообще \textbf{k}-факториала, которые он объединил в одно определение -- мультифакториал порядка \textbf{k}. \textit{Мультифакториалом} \textit{порядка} \textit{\textbf{k}} Вася назвал произведение всех целых чисел больших нуля, записанных начиная с заданного числа \textbf{n} в убывающем порядке, каждый сомножитель которого на \textbf{k} меньше предыдущего. Вот формульные представления этих терминов, придуманные Васей: \textbf{n! = n ∙ (n-1) ∙ (n-2) ∙ (n-3)...} \textbf{n!! = n ∙ (n-2) ∙ (n-4) ∙ (n-6)...} \textbf{n!!! = n ∙ (n-3) ∙ (n-6) ∙ (n-9)...} В общем виде формулу Вася записал так: \includegraphics{https://static.e-olymp.com/content/27/274694960ba3462478749dfbbe8ceb3362123c77.jpg} Чтобы приблизить вновь созданный раздел математики к школьной жизни, Вася заинтересовался вопросом: сколько разных делителей имеет заданный мультифакториал порядка \textbf{k}? \InputFile Первая строка содержит количество примеров в задании \textbf{N}. Единственная строка каждого примера содержит запись заданного мультифакториала. Известно, что числовая часть в его записи не превышает \textbf{1000}, а порядок \textbf{k} -- не больше \textbf{20}-ти. Известно также, что в одном тестовом примере нет двух одинаковых примеров. \OutputFile Для каждого тестового примера вывести в отдельной строке сначала его номер: \textbf{Sample i}: -- где \textbf{i} -- номер примера, а далее через пробел единственное число: количество делителей полученного значения мультфакториала порядка \textbf{k}. Если это количество превышает \textbf{10^18} Вася просит вывести придуманный им же символ бесконечности \textbf{oo}.