Після того, як Вася взнал на факультативі з програмування, що таке факторіал, у нього знову значно зріс інтерес до математики. Вирішивши залишити після себе слід у цій науці він придумав нову операцію -- мультифакторіал і тепер ретельно досліджує її. Для початку він увів поняття простого факторіалу. Згідно визначенню Васі, \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/49/491b14f9c6f8e29afc7b42b3269059895d3d1d16.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}.