In ancient Europe, people believed that their luck was dependent on a number. By summing up the digits of their birthday, they got a sum. By repeatedly adding the digits of the sum until a single digit number remains. This resultant number was called the "single digit representation". And the digit reflected their luck in their whole life.
In this question, a birthday will be given by a non-negative integer ~x~ (~\le 10\,000~ digits). Your program has to compute the single digit representation of the given number. Example:
~1 \to 1~
~10 \to 1+0 = 1~
~19 \to 1+9 = 10 \to 1~
~999 \to 9+9+9 = 27 \to 9~
The first input is an integer specifying the number of test cases. Then each input number appears on a line by itself.
For each test case, output the single digit representation of it.
4 1 10 19 999
1 1 1 9