16680번 - 안수빈수 스페셜 저지

자릿수의 합이란 무엇인가? 이는 수를 10진수로 나타내었을 때, 각 자리 숫자들의 합을 의미한다. 예를 들어, 1093의 자릿수의 합은 1 + 0 + 9 + 3 = 13이다.

우리는 자릿수의 합이 짝수인 양의 정수를 수빈수라고 부르기로 했다. 그리고 수빈수가 아닌 양의 정수를 안수빈수라고 부르기로 했다.

어떤 양의 정수 N이 주어졌을 때, N의 배수 중 안수빈수가 있는지 확인하고, 있다면 아무거나 하나를 출력하는 프로그램을 작성하시오.

첫 번째 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 1,000)

두 번째 줄 부터 T개의 줄에 걸쳐, 각각의 테스트 케이스에 대한 N이 주어진다. (1 ≤ N ≤ 100,000,000)

각 테스트 케이스에 대해 매 줄마다 아래와 같이 출력한다.

• N의 배수 중 안수빈수가 없다면 -1을 출력한다.
• N의 배수 중 안수빈수가 있다면, 그 중 10¹⁸ 이하의 안수빈수를 아무거나 하나 출력한다.

100,000,000 이하의 양의 정수 N에 대해, N의 배수 중 안수빈수가 있다면, 그 중 10¹⁸ 이하의 안수빈수가 존재함이 보장된다고 생각해도 좋다.