언덕수는 각 자릿수가 증가했다가 감소할 수는 있지만, 절대 감소했다가 증가하는 일은 없는 정수다.

• 12321은 언덕수다.
• 101은 언덕수가 아니다.
• 1111000001111은 언덕수가 아니다.

정수 N이 주어지면, N이 언덕수라면 N보다 작은 언덕수의 개수를 출력하고, 언덕수가 아니라면 -1을 출력하라.

입력 형식

첫째 줄에 테스트 케이스의 개수가 주어진다.

이어서 각 줄에 해당 테스트 케이스의 정수 N이 주어지며, N은 최대 70자리다. 답은 항상 64비트 long의 범위 안이 되도록 주어진다.

출력 형식

각 테스트 케이스마다 한 줄에 걸쳐 답을 출력한다.

예제 입력

5
10
55
101
1000
1234321

예제 출력

10
55
-1
715
94708