시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 128 MB 322 59 43 22.051%

문제

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

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

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

입력

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

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

출력

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

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

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

예제 입력 1

4
1000
1234
13
9

예제 출력 1

1000
7404
52
18

가능한 답이 여럿 있을 수도 있으므로, 꼭 예시 답안과 같게 나올 필요가 없음에 주의하시오.