Presti Digitator, the world-famous magician, is highly dissatisfied with his way of shuffling cards. Just yesterday, a perky guy in the audience demanded that he shuffle the cards once again, and he was aghast to see that the bottom card had not changed. Even though Mr. Digitator pacified the crowd with a few excellent tricks, the whole experience left him sad. He thinks that his shuffling leaves too many cards unchanged. He has decided to return to the drawing board, and retrain himself.

He thinks that a "good" shuffle should leave no card in its old position. Assume that cards are numbered sequentially starting from 1. For example, if there are 4 cards initially arranged in the order 1,2,3,4, a shuffle of 2,3,4,1 would be considered good, while 3,2,1,4 would be bad since 2 and 4 are unchanged in the shuffled order. Digitator wonders whether good shuffles are rare - he would like to know, how many good shuffles of a given deck of cards there are.

Input

For this question, you are given a series of numbers on distinct lines. The first line contains a number (let’s call it n) denotes how many decks there are to shuffle.

This is followed by n lines, each containing a positive number less than or equal to 20. Each such number denotes the number of cards in that deck.

Output

The output should have several lines. The i-th line is the number of good shuffles for the number of cards described in the i-th line. The output will fit inside a 64-bit integer.

Example

Input: 2 2 4 Output: 1 9
q2 Children are taught to add multi-digit numbers from right to left, one digit at a time.

Many find the “carry” operation, where a 1 is carried from one digit position to the
next, to be a significant challenge. Your job is to count the number of carry operations for each of a set of addition problems so that educators may assess their difficulty.

Input

Each line of input contains two unsigned integers less than 10 digits. The last line of input contains “0 0”.

Output

For each line of input except the last, compute the number of carry operations that result from adding the two numbers and print them in the format shown below.

Example

Input: 123 456 555 555 123 594 0 0 Output: No carry operation. 3 carry operations. 1 carry operation.