Background

A formal statement of the problem is given at the end of the description.

Problem Description

ZHY practices rap in an empty room.

At the beginning, ZHY makes a sound with intensity $x$. This sound collides with the walls and produces an echo with intensity $\lfloor \frac x {10} \rfloor$. The echo continues to collide with the walls, producing an echo of the echo... until the echo intensity becomes $0$.

There is also a radio in the room, which records all sounds (including the initial sound and all echoes). Unfortunately, ZHY accidentally broke the radio. Now, the radio can only display the sum of the intensities of all recorded sounds, $y$. Can you compute the intensity of ZHY's initial sound from this only information? Since the radio is very old, it may malfunction and show an incorrect number. In such cases, you need to output $-1$.

Formal statement

Define a function as follows:

$$f(x)=\begin{cases} 0 & x = 0 \\ x+f(\lfloor\frac{x}{10}\rfloor) & x > 0 \end{cases}$$

For example, $f(123)=123+12+1=136$.

Given a number $y$, determine whether there exists a unique number $x$ such that $f(x)=y$. If it exists, output $x$; otherwise, output $-1$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, denoting the number of test cases.

Each test case contains one line with an integer $y$.

Output Format

For each test case, if there exists a unique $x$ corresponding to this $y$, output $x$. Otherwise, output -1.

2
12
136

11
123

3
10
123
7510

-1
111
6761

Hint

$\mathrm{Subtask} \kern{2pt} \mathrm{id}$	$y$	Special property	Score
$1$	$< 1000$	None	$10$
$2$	$< 10^6$		$15$
$3$	$< 10^{100000}$	$S\le 9$	$10$
$4$		$S\le 10$	$20$
$5$	$< 10^{3000}$	None	$15$
$6$	$< 10^{500000}$		$30$

In the “Special property” column, $S\le k$ means: “If a solution exists, the sum of all digits of $x$ is at most $k$.”

For all testdata, $1\le T\le 10$, $0 \le y < 10^{500000}$.

Translated by ChatGPT 5