Vasya`s arithmetic 2
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 simple factorial given number n - the product of all integers greater than zero, recorded from a given number of n in descending order, each factor is one less than the previous one.
It is logical that Vasya introduced the concept of a 2-factorial 3-factorial, etc. and in general k-factorial, which he combined into one definition - multifactorial order k.
Multifactorials order k Vasya called the product of all integers greater than zero, recorded from a given number of n in descending order, to which each factor k is less than the previous one.
Here is the presentation of these definable term coined by Vasya:
n! = n ∙ (n-1) ∙ (n-2) ∙ (n-3)...
n!! = n ∙ (n-2) ∙ (n-4) ∙ (n-6)...
n!!! = n ∙ (n-3) ∙ (n-6) ∙ (n-9)...
In general, the formula so Vasya wrote:
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 k?
Input
The first line contains a number of examples in the job 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 1000, and the order k - no more than 20. We also know that in one test case no two identical examples.
Output
For each test case output a single line of his first number: Sample i: – where i – number of example, and then through the gap a single number: the number of divisors of reading multfactorials order k. If this number exceeds 10^18 Vasya asks to withdraw them as invented by the infinity symbol oo.