Ahn Subin Number

Time limit0.5sMemory limit128 MB

Summary

For each N up to 100,000,000, find a multiple of N whose decimal digit sum is odd, or print -1 if none exists.

Level: Medium6 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

The digit sum of a number is the sum of its digits when written in base 10. For example, the digit sum of 1093 is $1 + 0 + 9 + 3 = 13$ .

A positive integer whose digit sum is even is called a Subin number. A positive integer that is not a Subin number is called an Ahn Subin number.

Given a positive integer $N$ , write a program that checks whether a multiple of $N$ is an Ahn Subin number. If one exists, print any one of them.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 1,000$ ).

Each of the next $T$ lines contains one test case, an integer $N$ ( $1 \le N \le 100,000,000$ ).

Output

For each test case, print one line.

If no multiple of $N$ is an Ahn Subin number, print -1.
If a multiple of $N$ is an Ahn Subin number, print any one Ahn Subin number among those multiples that is at most $10^{18}$ .

For every positive integer $N$ up to 100,000,000, if a multiple of $N$ is an Ahn Subin number, then an Ahn Subin number at most $10^{18}$ is guaranteed to exist.

Examples1

Example 1
Input
```
4
1000
1234
13
9
```
Expected output
```
1000
7404
52
18
```