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