The digital root (also repeated digital sum) of a non-negative integer is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.
For example, the digital root of 65,536 is 7, because 6 + 5 + 5 + 3 + 6 = 25 and 2 + 5 = 7.
Your job is to calculate the digital root.
The first line is N, means there are N test cases.
Following N lines, each line contain a non-negative integer m (1<=m<=1050)
For each line output the digital root.
3 24 39 987654321
6 3 9