This problem was used in the following GFU competitions:
GFU 2024 D1 Q8
“Drat!” cursed Charles. “This stupid carry bar is not working in my Engine! I just tried to calculate the square of a number, but it’s wrong; all of the carries are lost.”
“Hmm,” mused Ada, “arithmetic without carries! I wonder if I can figure out what your original input was, based on the result I see on the Engine.”
Carryless addition, denoted by ⊕ , is the same as normal addition, except any carries are ignored (in base 10). Thus, 37 ⊕ 48 is 75, not 85.
Carryless multiplication, denoted by ⦻, is performed using the traditional algorithm for multiplication, column by column, but the intermediate additions are calculated using carryless addition. More formally, Let amam-1 . . . a1a0 be the digits of a, where a0 is its least significant digit. Similarly define bnbn-1 . . . b1b0 be the digits of b. The digits of c = a ⦻ b are given by the following equation:
ck = a0bk ⊕ a1bk-1⊕ . . . ⊕ ak-1b1 ⊕ akb0
where any ai or bj is considered zero if i > m or j > n. For example, 9 ⦻ 1234 is 9876, 90 ⦻ 1234 is 98760, and 99 ⦻ 1234 is 97536.
Given N, find the smallest positive integer a such that a ⦻ a = N.
The first line will contain a single integer t that indicates the number of test cases that follow. The next t test cases will each consist of a single integer N, with at most 25 digits and no leading zeros.
For each test case, output on a single line, the least positive number a such that a ⊕ a = N. If there is no such a, print ‘-1’ instead.
Example Input:
4
6
149
123476544
15
Example Output:
4
17
11112
-1