Mr. Ong wants to develop a factorial generator machine, which input takes as a 62-bit integer, and output is a factorial of the given input. However, his main concern is memory consumption. He developed a factorial generator machine that input and output both are 62-bit integers. If an input generates more than 62-bit integers, it truncates to zero value, and other cases produce the factorial of the given number. Now, write a program that takes an input and produces the output based on a factorial generator machine.

Input

Input starts with an integer number T (T <= 20), the number of test cases. The following T line contains a 62-bit integer V (0 <= V <= 4611686018427387903).

Output

For each test case, first, print the serial number of the test case along with the factorial for the given input number. Check sample input and output for details.