After Vasya found out on course on programming that is factorial, it has again significantly increased interest in mathematics. Deciding to leave a mark in this science, he coined a new operation - multifactorial and now thoroughly examine it. To begin with, he dramatically introduced the concept of a simple factorial. According to the definition Vasya's, a \textit{simple factorial} given number \textbf{n} - the product of all integers greater than zero, recorded from a given number of \textbf{n} in descending order, each factor is one less than the previous one. It is logical that Vasya introduced the concept of a \textbf{2}-factorial \textbf{3}-factorial, etc. and in general \textbf{k}-factorial, which he combined into one definition - multifactorial order \textbf{k}. \textit{Multifactorials order} \textbf{k} Vasya called the product of all integers greater than zero, recorded from a given number of \textbf{n} in descending order, to which each factor \textbf{k} is less than the previous one. Here is the presentation of these definable term coined by Vasya: \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)...} In general, the formula so Vasya wrote: \includegraphics{https://static.e-olymp.com/content/9c/9cf6cdc3bd318409e77182502aef7a7d165830d2.jpg} To bring the newly created branch of mathematics in school life, Vasya became interested in the question: how many different subgroups of a given order multifactorial \textbf{k}? \InputFile The first line contains a number of examples in the job \textbf{N}. The only line of each example contains a record set multifactorials. It is known that the numeric part of his record does not exceed \textbf{1000}, and the order \textbf{k} - no more than \textbf{20}. We also know that in one test case no two identical examples. \OutputFile For each test case output a single line of his first number: \textbf{Sample i}: -- where \textbf{i} -- number of example, and then through the gap a single number: the number of divisors of reading multfactorials order \textbf{k}. If this number exceeds \textbf{10^18} Vasya asks to withdraw them as invented by the infinity symbol \textbf{oo}.