Digit Sum of N Numbers

Source: Phước Hưng OJ

Problem Statement

Given t nonnegative integers, compute the sum of decimal digits of EACH integer separately. For example, 305 has digit sum 3+0+5=8. The digit sum of 0 is 0. Do not combine different input integers into one total.

Input

The first line contains integer t. The remaining input contains exactly t integers a_1,...,a_t, separated by whitespace; they may span multiple lines.

Output

Print exactly t lines; line i contains the digit sum of a_i, with no additional text.

Subtasks

• Subtask 1 (20%): 1 <= t <= 5 and 0 <= a_i <= 1000.
• Subtask 2 (30%): 1 <= t <= 200 and 0 <= a_i <= 10^6.
• Subtask 3 (50%): 1 <= t <= 10000 and 0 <= a_i <= 10^9.

Examples

Example 1

Input:

4
0 305 999 10

Output:

0
8
27
1

Explanation:

Zero gives 0; 305 gives 3+0+5=8; 999 gives 27; 10 gives 1.

Example 2

Input:

2
1000000000
1005

Output:

1
6

Explanation:

10^9 has one digit 1 and nine zeros, giving 1; 1005 gives 6.