Once there was a Shikaari in IIIT Delhi campus and he was famous for his Shikaar techniques. Also there was Kalakhatta who was jealous of Shikaari’s charisma. Once Kalakhatta challenged Shikaari to test his knowledge. Now Shikaari’s afraid of losing, would you help?

You are given a number N and you have to increment the most significant digit without changing any other number in N. You can do this by adding a positive number X.

Input

The first line of the input consist of a single integer number T which determines the number of tests.

In each of next t lines there is a single integer number N.

Constraints

• 0 < t ≤ 10⁵
• | n | ≤ 10⁹

Output

Print the minimum number X in separate lines.

Example

Input:
2
5
15
Output:
1
10