## Problem: Faulty Keyboard

*Difficulty: Eazy

Ritesh has found out a keyboard from his store room which is very unique. Unique because the keyboard contains only 10 keys (the numpad). In other words the keyboard has 10 keys, they are 1,2,3,4,5,6,7,8,9,0.

Sharat has got the task to type all the natural number from 1 to N, using this keyboard. But the keyboard is in damaged condition, means, after pressing M keys in total from the keyboard, the keyboard completely stops working.

Now you being his friend need to find out the greatest natural number he can type using the keyboard starting from 1. (You need to find the value of N).

Input

The first line of input contains the integer T, where T is the number of test cases. Then T test cases follow. Each test case contains an integer M, where M is maximum number of keys he can press in the keyboard before its completely damaged.

Output:

In each test case print a single integer N,where N is the greatest natural number he can type using the keyboard starting from 1.

Constraints:

0 < T < 105

0 < M < 38890

Example:

Input:

3

5

10

15

Output:

5

9

12

Explanation:

(i)For the 1st test case M=5, he can type 1 2 3 4 5. Now after pressing 5 keys the keyboard is damaged.

(ii)For the 2nd test case M=10, he can type 1 2 3 4 5 6 7 8 9, he has pressed 9 keys and can press only 1 more key but the next natural number he needs to type is 10, which is 2 digit, so he cant type 10, thus the greatest natural number he can type starting from 1 is 9.

(iii)For the 3rd test case M=15, he can type 1 2 3 4 5 6 7 8 9 10 11 12, now he has pressed 15 keys and the keyboard is damaged. Thus the greatest natural number he can type starting from 1 is 12.

Implementation: Python 2.7

# there are 9 1-digit number

# 90 2-digit number

# 900 3-digit number

# so on

numbers = [0, 9, 90*2, 900*3, 9000*4]

def find_n(number_of_keys):

n = 9

if number_of_keys <= numbers[1]:

return number_of_keys

elif number_of_keys <= numbers[2]+numbers[1]:

number_of_keys -= 9

n += number_of_keys/2

elif number_of_keys <= numbers[3]+numbers[2]+numbers[1]:

number_of_keys -= 9

n += numbers[2]/2

number_of_keys -= numbers[2]

n += number_of_keys/3

elif number_of_keys <= numbers[4]+numbers[3]+numbers[2]+numbers[1]:

number_of_keys -= 9

n += numbers[2]/2

number_of_keys -= numbers[2]

n += numbers[3]/3

number_of_keys -= numbers[3]

n += number_of_keys/4

return n

if __name__ == '__main__':

t = input()

for _ in xrange(t):

m = input()

print find_n(m)

## Reply