Digital Root Computation

Given a non-negative integer \(n\), its digital root is obtained by repeatedly summing its digits until a single-digit number is produced. For example, the digital root of \(38\) is computed as follows:

\(3+8=11\) then \(1+1=2\), so the digital root is \(2\).

Your task is to compute the digital root for each of \(T\) numbers.

inputFormat

The first line of input contains an integer \(T\) \( (1 \leq T \leq 10^5)\), representing the number of test cases. Each of the following \(T\) lines contains a non-negative integer \(n\) \( (0 \leq n \leq 10^{18})\).

outputFormat

For each test case, output a single line containing the digital root of the given number.

## sample

1
38

2

</p>