파아사 수

파폴 수는 모든 자리 숫자가 바로 왼쪽 자리 숫자보다 작은 양의 정수이다. 맨 앞자리는 왼쪽에 숫자가 없으므로 조건을 따지지 않는다. 왼쪽에서 오른쪽으로 읽으면 숫자가 계속 떨어져서 붙은 이름이다. 987654321이 파폴 수이다.

파아사 수는 조건이 조금 느슨하다. 모든 자리 숫자가 바로 왼쪽 자리 숫자보다 작거나 같은 양의 정수를 파아사 수라고 한다. 즉 왼쪽에서 오른쪽으로 읽을 때 숫자가 같은 값으로 이어져도 된다. 9987765321이 파아사 수이다.

파아사 수라고 해서 파폴 수인 것은 아니다. 반대로 파폴 수는 모두 파아사 수이다.

모든 파아사 수를 작은 것부터 차례대로 적은 목록을 만들려고 한다. 목록 전체를 적기에는 자리가 모자라니, N번째 파아사 수만 구하면 된다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어지는 T개의 줄에는 각각 정수 N이 하나씩 주어진다.

제한

• $1 \le T \le 10^4$
• $1 \le N \le 10^{18}$

각 테스트 케이스마다 N번째 파아사 수를 한 줄에 하나씩 출력한다.