TA1 - Addicted Numbers

no tags 

Anshuman was playing a game. The game consists of following steps

  1. He summed all the digits of a number.
  2. Until the sum became less than 10, he repeats the above step for the new number i.e. sum of all the digits of the number.

As the numbers are very large you have to help him figure out the final output of the game.

Input

First line of the input contains an integer t, 1<=t<=10 denoting the number of test cases, followed by t lines each containing a number n, 1<=n<=10^300000

Output

For each number n given at input, display a line with the final number.

Example

Input:
2
12345
213413512

Output:
6
4

For first test case:

  • 1+2+3+4+5=15
  • 1+5=6


Added by:Sandeep Singh
Date:2012-12-05
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64