# Digital Root

1000ms    65536K
548    182
Beginner

Description

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.

Input

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)

Output

For each line output the digital root.

Sample Input

3
24
39
987654321

Sample Output

6
3
9

Source

Editor

keefo on 2015-01-07 07:02:16