403163: GYM101055 F Alexandria's Oracle

Every self-respecting computer scientist knows the book "The Hitchhiker's Guide to the Galaxy" and knows the fundamental answer to life, the universe and everything. However what few know is that Douglas Adams' story is based on an Egyptian legend, of an oracle in the city of Eskendereyya (Alexandria).

In ancient times, the city founded in 331 BC by Alexander the Great was one of the main cities in the world, housing the Lighthouse of Alexandria (one of the seven wonders of the ancient world), the Great Library (the largest one of its time) and many other fantastic works. Legend says that Alexandria's Oracle lived there. The citizens of Alexandria would hand to the oracle small notes with two numbers, and receive another note back, that would be the fundamental answer of the universe related to the two numbers given.

In his treaty in 227 AC, Cleomenes of Naucratis (administrator of Alexandria while Alexander went to conquest) reported a few results obtained by the oracle:

• Given 8 and 1 the oracle returned 5040;
• Given 10 and 3, returned 280;
• Given 4 and 2, returned 8;
• Given 21 and 19, returned 42.

Modern studies show that the oracle returned a generalization of the factorial of an integer number. As we know,

The oracle returned, given N and K, the K-factorial of N, that is,

in which the product was done while the diference is greater or equal to 1. We can represent the K-factorial of a number as that number followed by K exclamation points:

• 8! = 5040;
• 10!!! = 280;
• 4!! = 8;
• 21!!!!!!!!!!!!!!!!!!! = 42

It is said that after reading about the oracle of Eskendereyya, Douglas Adams was inspired to do his work. Also, in Egypt is also the inspiration behind The Restaurant at the End of the Universe, but that is a story for another time...

Your task is to determine the answer the oracle gave to some notes.

The first line has a single integer Q, the number of queries.

The next Q lines each has an integer N followed by some exclamation points.

Limits

• 1 ≤ Q ≤ 200
• 1 ≤ N ≤ 100
• Each number will be followed by at least 1 and at most 20 exclamation points
• The answer of each query is guaranteed to be at most 10¹⁸

For each query, print the requested number.

4
3!
10!!!
19!!!!
4!!

6
280
65835
8