Tom is very fond of adding values , so what he does whenever he gets a value he adds all its digits and forms a new value and checks it whether it has become a single digit or not and if it does not even becomes a single digit he apply the operation again and adds all its digits once again and he continues to do this process repeat and repeat until he gets a single digit.

Input
First line of input contains the number of test cases(T). Next each of T lines contains a integer value.

Output
You have to print the single digit answer for each test case.

Constraints
1<T ≤ 100
1<value ≤ 10^5

SAMPLE INPUT
3
167
569
102

SAMPLE OUTPUT
5
2
3

Explanation

167 = 1+6+7 = 14 = 1+4 = 5
569 = 5+6+9 = 20 = 2+0 = 2
102 = 1+0+2 = 3

见题面

见题面