One of the most important aspects of being a good competitive programmer is the ability to handle very large numbers. Kashyap knows this and decides to solve basic problems concerning very large numbers. His first target is to find the sum of digits of very large numbers to single digit. To simplify his task, he decides to have numbers whose unit digit will never be zero. Help him accomplish his task.

Input

First line of the input contains the number of test cases t (1 <= t <= 130). Then t test cases follow. Each of the following t lines contain a very large number n (1 <= n <= 10^10000000).

Output

For each test case, print a line denoting the sum of digits of the given number, reduced down to single digit.

Example

Input:
2
123
999

Output:
6
9

Explanation

1. 1 + 2 + 3 = 6
2. 9 + 9 + 9 = 27 = 2 + 7 = 9