# Digital Root

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<=10^{50})

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