The first line contains an Integer 'T' which denotes the number of test cases/queries to be run.
Then the test cases follow.
The first line of input for each test case/query contains an integer N, the Nth number to find.
For each test case, print the Nth positive integer whose sum of digits equals 10.
Output for every test case will be printed in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 100
1 <= N <= 10^7
Time Limit: 1sec
The Idea is to use binary search to find the Nth Number with a digit sum equal to 10. For this to calculate, we will do a binary search in the possible range(1 to MAX) where MAX denotes the Maximum number possible(LONG_MAXVALUE). For each MID value, we will find the count of numbers less than or equals MIN with digit sum equals 10. If the count equals N we will mark the MID value as the answer and check for the left part of our search to find the exact Nth number. Similarly, if the count is greater than N we need to decrease the possible range (search to the left side). Otherwise, if the count is smaller than N, we will move to the right part of our search to include more such numbers.
Now, to find all numbers less than a particular number say X, with digit sum 10, we iterate the number by replacing its digits such that it is less than X. If this number satisfies the property, increment the count. To iterate the number we will start from the Most Significant Bit and set all possible bits at this place and call for the next most significant bit.
Forex, lets say X = 485.
Now Most significant bit = 4 to iterate over all possible numbers we will set SMALLER = 1 which will tell us that the limit of the current bit equals the value of that bit in X. So we can choose the most significant bits as 0,1,2,3 and while choosing 4 we will update limit. Similarly, we can keep iterating on the next bits.
Given below is the pseudocode on how we will calculate this recursively.
Pseudocode:

Note: This approach will always give TLE even for small numbers. As in the binary search we have chosen large numbers(LONG_MAX) due to uncertainty for the Nth number.
The Idea is to use binary search to find the Nth Number with a digit sum equal to 10. For this to calculate, we will do a binary search in the possible range(1 to MAX) where MAX denotes the Maximum number possible(LONG_MAXVALUE). For each MID value, we will find the count of numbers less than or equals to MIN with digit sum equals to 10. If the count equals N we will mark the MID value as the answer and check for the left part of our search to find the exact Nth number. Similarly, if the count is greater than N we need to decrease the possible range( search to the left side). Otherwise, if the count is smaller than N, we will move to the right part of our search to include more such numbers.
Now, to find all numbers less than a particular number say X, with digit sum 10. As we iterated on all numbers using recursion. Here we will use memoization to avoid calculating repeated subproblems. The idea is similar to digit dp as discussed![here](https://codeforces.com/blog/entry/53960)
Pseudocode:

Find minimum
Randomly Sorted
Search In A Sorted 2D Matrix
8Queen Problem
Fake Coin Problem