cho.sh

Paasa Numbers

Find the Nth positive integer whose digits never increase from left to right, given N up to 10^18 and 10^4 queries.

Medium6CombinatoricsDynamic programmingMathBinary searchNo attempts yetTime limit3sMemory limit512 MB

Problem

A pafall number is a positive integer in which every digit is smaller than the digit immediately to its left. The leading digit has nothing to its left, so no condition applies to it. The name comes from the way the digits fall as you read the number from left to right. 987654321 is a pafall number.

A paasa number relaxes that condition. A positive integer is a paasa number when every digit is smaller than or equal to the digit immediately to its left, so the digits may also stay level as you read from left to right. 9987765321 is a paasa number.

A number can be paasa without being pafall. Every pafall number, on the other hand, is paasa.

You want a list of all paasa numbers written in increasing order. Writing out the whole list would take more room than you have, so you only need one entry: given N, report the Nth paasa number.

Input

The first line contains T, the number of test cases. Each of the following T lines contains a single integer N.

Constraints

  • 1≤T≤1041 \le T \le 10^4
  • 1≤N≤10181 \le N \le 10^{18}

Output

For each test case, print the Nth paasa number on its own line.