Touka is fan of big numbers, so when her friend kuroko gives her a positive number \(N\) she calculates \(M=2^N\)(2 raised to power N) and tell it to him .But since \(M\) can be very large so it is very difficult for her to tell it to kuroko. So she decides to calculate the sum of digits of \(M\) till she gets a single digit number and tells it to kuroko.
Touka is very tired of the calculation and needs your help to calculate it for her.
Her friend kuroko asks her \(T\) queries.
In each query you will be given \(N\) as input.
Print the answer reqired in each query.

Example

Let's assume that \(N\)=6 then \(M\) = \(2^6\) = 64.

Now 6+4=10. Since it's still not a single digit so we add digits of 10 i.e 1+0=1, which is the required answer.

Function Description

Complete the solve function provided in the editor. This function takes the following 1 parameter and returns the sum of digits of \(M\) untill its a single digit number.

\(N\): Represents an integer denoting \(N\).

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line has an integer \(T\) denoting the number of test cases.
For each test case:
- The only line has an integer \(N\).

Output format

Print \(T\) lines each corresponding to the answer to each query.

Code snippets

Code snippets are written in languages C, C++, Java, Python.

Constraints

\(1 <= T <= 100\)
\(0 <= N <= 100000\)