In Computer Science, Trie or prefix tree is a data structure which is usually used to store strings or numbers. Unlike binary trees, edges contain characters. And a node actually represents a string which is found by taking the characters from the edges, in the path from root to leaf. For example, for {abc, ae, bd, bb, bc, abd} we get the following trie:

Now you are given a set of strings and each string uses one of the K character symbols, and in any string (from the set) a symbol occurs at most once. Your task is to find the number of nodes required if we make a trie with the strings using the procedure described above. As you don't know the size of the set, your task is to find the worst case result. For example, if you have 2 character symbols, then you need 5 nodes in worst case as in the following trie (let the symbols be {a, b}):

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer K (1 ≤ K ≤ 10⁸).

For each case, print the case number and the total number of nodes required in worst case. The result can be big, print the least 4 significant digits if result has 4 or more digits, otherwise, print the result.

• The least 4 significant digits of 123456789 is 6789.