Given a number N .Add the digits in it until it becomes single digit.

For Example: 

N=972

sum=9+7+2=18

sum=9

So print 9

Input:

First line of input cotains T denoting number of test cases

Next T lines contains an integer N

Output :

Print T new Lines sum of digits of a number until single digit

Constraints :

$1<=T<=30$

$1<=N<=10^6$