LDIGSUM - Large Digit Sum

no tags 

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


Added by:kousik
Date:2013-08-24
Time limit:0.400s-0.800s
Source limit:1500B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA PYTHON PYTHON3 PY_NBC RUBY
Resource:Own