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 ( digits). Your program has to compute the single digit representation of the given number. Example:
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