Math Problem

Interview

Time limit1sMemory limit1024 MB

Summary

For each N, find the smallest X such that N plus the digit sum of X equals X, or report -1 if none exists.

Level: Medium5 of 10
Topics: Math, Implementation, Brute force, Number theory
Solved: No attempts yet

Problem

The blackboard has some numbers written on it whose sum is N. Jongyeong was ordered by the teacher to write down the sum of all the numbers on the blackboard. Jongyeong confidently wrote N, but writing N increased the sum of the numbers, so he was scolded. Fed up, Jongyeong gave up and decided to ask you to handle this. Solve the problem on Jongyeong's behalf.

In other words, for a given N, find the smallest X such that N + (sum of the digits of X) = X. Once is too easy, so handle it T times to prepare in advance for the teacher's attacks.

Input

The first line gives T. (1 ≤ T ≤ 10^6)

The next T lines each give N for one problem. (1 ≤ N ≤ 10^9)

Output

Separate the answers with spaces and print them in order. If no valid answer exists, print -1.

Examples1

Example 1
Input
```
3
9
10
99
```
Expected output
```
10 -1 100
```