Replace every non-negative array value by the sum of its decimal digits.

Input

The first line contains \(n\). The second line contains \(n\) non-negative integers.

The input satisfies:

• \(0 <= n <= 1000\)

Output

Print the digit sums in input order, separated by spaces.

Example

Input

6
512 123 234 4522 3 112

Output

8 6 9 13 3 4