Let's call a positive integer extremely round if it has only one non-zero digit. For example, $5000$, $4$, $1$, $10$, $200$ are extremely round integers; $42$, $13$, $666$, $77$, $101$ are not.

You are given an integer $n$. You have to calculate the number of extremely round integers $x$ such that $1 \le x \le n$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Then, $t$ lines follow. The $i$-th of them contains one integer $n$ ($1 \le n \le 999999$) — the description of the $i$-th test case.


-----Output-----

For each test case, print one integer — the number of extremely round integers $x$ such that $1 \le x \le n$.


-----Examples-----

Input
5
9
42
13
100
111
Output
9
13
10
19
19


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Implementation

Complete search


Solutions:
for (x, *r) in [*open(0)][1:]:
	print(9 * len(r) - 9 + int(x))


i = int(input())
f = []
for t in range(i):
	q = input()
	f.append((len(q) - 1) * 9 + int(q[0]))
[print(a) for a in f]


for n in [*open(0)][1:]:
	print(9 * len(n) - 18 + int(n[0]))


import sys

def in_int():
	return int(sys.stdin.readline())

def in_str():
	return sys.stdin.readline().rstrip()

def in_map_int():
	return map(int, sys.stdin.readline().split())

def in_arr_int():
	return list(map(int, sys.stdin.readline().split()))

def in_arr_str():
	return sys.stdin.readline().split()

def is_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return True
	return False

def solve(n):
	if n <= 9:
		return n
	if 9 < n <= 99:
		return 9 + n // 10
	if 99 < n <= 999:
		return 18 + n // 100
	if 999 < n <= 9999:
		return 27 + n // 1000
	if 9999 < n <= 99999:
		return 36 + n // 10000
	if 99999 < n <= 999999:
		return 45 + n // 100000

def main():
	t = in_int()
	for _ in range(t):
		n = in_int()
		print(solve(n))
main()


import sys
input = sys.stdin.readline

def print_str_line(str):
	sys.stdout.write(str + '\n')

def print_number(number):
	print_str_line(f'{number}')

def ans(n):
	ans_result = 0
	factor = 10
	while factor < n:
		ans_result += 9
		factor *= 10
	ans_result += n // (factor // 10)
	return ans_result
number_of_inputs = int(input())
for i in range(number_of_inputs):
	_input = int(input())
	_ans = ans(_input)
	print(_ans)


import sys, math
input = sys.stdin.readline
INF = int(1000000000.0) + 7

def solve():
	n = int(input())
	ans = 9 * (len(str(n)) - 1) + int(str(n)[0])
	print(ans)
t = 1
t = int(input())
for i in range(1, t + 1):
	solve()


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	m = len(str(n))
	return n // pow(10, m - 1) + (m - 1) * 9
for _ in range(int(input())):
	print(solve())


t = int(input())
res = []
for i in range(t):
	n = int(input())
	if n < 11:
		res.append(n)
		continue
	if n < 101:
		res.append(n // 10 - 1 + 10)
		continue
	if n < 1001:
		res.append(n // 100 - 1 + 19)
		continue
	if n < 10001:
		res.append(n // 1000 - 1 + 28)
		continue
	if n < 100001:
		res.append(n // 10000 - 1 + 37)
		continue
	if n < 1000001:
		res.append(n // 100000 - 1 + 46)
for j in res:
	print(j)


n = int(input())
arr = []
for i in range(n):
	x = int(input())
	if x < 10:
		arr.append(x)
	else:
		total = 0
		nearest = len(str(x)) - 1
		x = int(x / 10 ** nearest)
		total += nearest * 9
		total += x
		arr.append(total)
for i in arr:
	print(i)


t = int(input())
loo = []
for i in range(t):
	n = int(input())
	if 1 <= n <= 9:
		loo.append(n)
	if 10 <= n <= 99:
		loo.append(9 + n // 10)
	if 100 <= n <= 999:
		loo.append(18 + n // 100)
	if 1000 <= n <= 9999:
		loo.append(27 + n // 1000)
	if 10000 <= n <= 99999:
		loo.append(36 + n // 10000)
	if 100000 <= n <= 999999:
		loo.append(45 + n // 100000)
for i in range(t):
	print(loo[i])


import sys
input = sys.stdin.readline

def sol(n):
	tmp = n
	cnt = 0
	while tmp >= 10:
		cnt += 1
		tmp //= 10
	return cnt * 9 + tmp
t = int(input())
for case in range(t):
	n = int(input())
	print(sol(n))


import math
import string
from bisect import bisect, bisect_left, bisect_right
from itertools import accumulate, combinations, permutations
from collections import Counter
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	if n < 10:
		print(n)
	else:
		l = len(str(n))
		print(n // 10 ** (l - 1) + (l - 1) * 9)


def main():
	t = int(input())
	results = []
	for _ in range(t):
		n = input()
		result = (len(n) - 1) * 9 + int(n[0])
		results.append(result)
	return results
results = main()
for result in results:
	print(result)


import math
import sys

def solve():
	input = sys.stdin.readline
	n = int(input())
	ans = min(n, 9) + min(n, 99) // 10 + min(n, 999) // 100 + min(n, 9999) // 1000 + min(n, 99999) // 10000 + min(n, 999999) // 100000 + min(n, 9999999) // 1000000 + min(n, 99999999) // 10000000 + min(n, 999999999) // 100000000 + min(n, 9999999999) // 1000000000
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def main():
	result = []
	t = int(input())
	for test in range(t):
		n = [int(x) for x in input()]
		extremely_round = n[0] + 9 * (len(n) - 1)
		result.append(extremely_round)
	print(*result, sep='\n')
main()


import math
t = int(input())
result = []
for i in range(t):
	n = int(input())
	k = int(math.log10(n))
	a = (n - n % 10 ** k) // 10 ** k
	result.append(a + 9 * k)
print(*result, sep='\n')


import math

def ans(n):
	if n <= 9:
		return n
	c = 0
	k = n
	while n != 0:
		n = n // 10
		c += 1
	d = int(math.pow(10, c - 1))
	return 9 * (c - 1) + k // d
t = int(input())
l = []
for i in range(t):
	n = int(input())
	l.append(ans(n))
for i in range(t):
	print(l[i])


import math
lines = []
t = int(input())
x = 0
while x < t:
	y = int(input())
	digits = int(math.log10(y)) + 1
	if digits == 1:
		z = y
	else:
		z = int(y / 10 ** (digits - 1))
	n = 9 * (digits - 1) + z
	x += 1
	lines.append(n)
for n in lines:
	print(n)


import math

def round_nos(n):
	j = int(math.log10(n))
	k = n // 10 ** j + 9 * j
	return k
n = int(input())
nums = []
for i in range(n):
	nums.append(int(input()))
for no in nums:
	print(round_nos(no))


a = int(input())
list1 = []
for i in range(a):
	n = int(input())
	if n < 11:
		list1.append(n)
	elif n > 10 and n <= 100:
		summa = n // 10 + 9
		list1.append(summa)
	elif n > 100 and n < 200:
		n = str(n)
		n = int(n[0]) + (len(n) - 1) * 9
		list1.append(n)
	elif n >= 200:
		n = str(n)
		n = int(n[0]) + (len(n) - 1) * 9
		list1.append(n)
i = 0
for i in range(len(list1)):
	print(list1[i])


import math
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque

def test_case():
	a = list(map(int, list(input())))
	ans = 0
	for i in range(len(a)):
		if i == 0:
			ans += a[i]
		else:
			ans += 9
	print(ans)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		test_case()
main()


import sys
input = sys.stdin.readline
K = int(input())
for _ in range(K):
	n = input().rstrip()
	if len(n) == 1:
		print(n)
	else:
		print((len(n) - 1) * 9 + int(n[0]))


x = []
n = int(input())
for i in range(n):
	num = int(input())
	a = str(num)[0]
	if num <= 10:
		x.append(num)
	else:
		b = len(str(num))
		z = (b - 2) * 9 + 10 + int(a)
		x.append(z - 1)
for item in x:
	print(item)


def superround(a):
	s1 = 9 * (len(a) - 1)
	s2 = int(a) // 10 ** (len(a) - 1)
	return s1 + s2

def main():
	t = int(input())
	lst = []
	for i in range(t):
		n = int(input())
		kolvo = superround(str(n))
		lst.append(kolvo)
	for item in lst:
		print(item)
main()


a = int(input())
for _ in range(a):
	b = int(input())
	if b > 100000:
		print(45 + b // 100000)
	elif b > 10000:
		print(36 + b // 10000)
	elif b > 1000:
		print(27 + b // 1000)
	elif b > 100:
		print(18 + b // 100)
	elif b > 10:
		print(9 + b // 10)
	else:
		print(b)


t = int(input())
iterlist = []
i = 0
while i < t:
	n = input()
	string_length = len(n)
	if string_length == 1:
		iterlist.append(int(n))
	else:
		a = 9 * (string_length - 1)
		iterlist.append(a + int(n[0]))
	i += 1
j = 0
while j < len(iterlist):
	print(iterlist[j])
	j += 1


t = int(input())
A = []
for i in range(t):
	n = int(input())
	m = n
	cont = 0
	if n < 10:
		A.append(n)
	else:
		s = str(n)
		n = n - int(s[1:])
		ceros = str(n).count('0')
		r = 9 * ceros + m // int(str(1) + '0' * ceros)
		A.append(r)
for i in A:
	print(i)


def countDigit(n):
	count = 0
	while n != 0:
		n //= 10
		count += 1
	return count
t = int(input())
arr = []
while t > 0:
	n = int(input())
	arr.append(n)
	t -= 1
print('\n')
res = []
for i in arr:
	if i <= 10:
		res.append(i)
	else:
		base = 10 ** (countDigit(i) - 1)
		modX = i - i % base
		x = 9 * (countDigit(i) - 1) + modX // base
		res.append(x)
for num in res:
	print(num, end='\n')


import sys
from bisect import bisect_left as bl, bisect_right as br, bisect
from collections import defaultdict as dd, deque, Counter
from heapq import merge, heapify, heappop, heappush, nsmallest
from itertools import combinations
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log

def inp():
	return sys.stdin.readline().strip()

def iinp():
	return int(inp())

def mp():
	return map(int, inp().split())

def liinp():
	return list(mp())

def ls():
	return list(inp())

def out(arr):
	return ' '.join(map(str, arr))

def out2D(arr):
	return '\n'.join((' '.join(map(str, n)) for n in arr))

def l1D(n, val=0):
	return [val for _ in range(n)]

def l2D(n, m, val=0):
	return [l1D(m, val) for _ in range(n)]

def solve(n):
	if len(str(n)) == 1:
		return n
	return 9 + solve(n // 10)
tc = iinp()
for _ in range(tc):
	n = iinp()
	print(solve(n))


n = int(input())
for i in range(n):
	k = input()
	print(int(k[0]) + 9 * (len(k) - 1))


t = int(input())
for _ in range(t):
	n = input()
	len_ = len(n)
	if len_ == 1:
		print(n)
	else:
		print(int(n[0]) + 9 * (len_ - 1))


test = int(input())
out = []
for i in range(test):
	x = str(input())
	count = 0
	y = x[0]
	for i in range(len(x) - 1):
		y += '0'
	if y[0] == '1':
		zeros = len(y) - 1
		count = zeros * 9 + 1
	else:
		count = int(y[0])
		zeros = len(y) - 1
		count = count + zeros * 9
	out.append(count)
	count = 0
for i in out:
	print(i)


for _ in range(int(input())):
	n = input()
	ans = int(n[0]) + (len(n) - 1) * 9
	print(ans)


import math
import sys
import re
lines = sys.stdin.readlines()
nums = []
for (line_index, line) in enumerate(lines):
	if line_index == 0:
		NUM_EFFECTIVE_LINES = int(re.fullmatch('(\\d+)\n', line)[1])
		continue
	p = '(\\d+)\n'
	m = re.fullmatch(p, line)
	n = m[1]
	nums += [n]
assert len(nums) == NUM_EFFECTIVE_LINES

def solve(n):
	num_digits = len(n)
	high_digit_val = int(n[0])
	return (num_digits - 1) * 9 + high_digit_val
for n in nums:
	ans = solve(n)
	print(ans)


t = int(input())
while t > 0:
	n = input()
	l = len(n)
	ans = 0
	ans += int(n[0])
	l -= 1
	ans += 9 * l
	print(ans)
	t -= 1


for hm in range(int(input())):
	a = input()
	b = len(a)
	x = 0
	j = a[0]
	print(9 * (b - 1) + int(j))


for _ in range(int(input())):
	n = int(input())
	if n <= 10:
		print(n)
	elif n < 100:
		print(9 + n // 10)
	elif n < 1000:
		print(18 + n // 100)
	elif n < 10000:
		print(27 + n // 1000)
	elif n < 100000:
		print(36 + n // 10000)
	elif n < 1000000:
		print(45 + n // 100000)


for _ in range(int(input())):
	n = input()
	if len(n) == 1:
		print(n)
		continue
	print((len(n) - 1) * 9 + int(n[0]))


t = int(input())

def solve(n):
	k = len(n)
	return (k - 1) * 9 + int(n[0])
for i in range(t):
	print(solve(input()))


for _ in range(int(input())):
	a = input()
	b = 9 * (len(a) - 1) + int(a[0])
	print(b)


for t in range(int(input())):
	x = int(input())
	count = 0
	while x > 10:
		count += 9
		x = x // 10
	count += x
	print(count)


class Finding_round:

	def round(t):
		for i in range(t):
			x = int(input())
			count = 0
			while x > 10:
				count += 9
				x = x // 10
			print(count + x)
t = int(input())
Finding_round.round(t)


for loop in range(int(input())):
	n = input()
	print((len(n) - 1) * 9 + int(n[0]))


t = int(input())
for _ in range(t):
	n_str = input()
	n = int(n_str)
	if n <= 10:
		print(n)
	else:
		print(9 * (len(n_str) - 1) + int(n_str[0]))


t = int(input())
for i in range(t):
	n = int(input())
	cnt = 0
	a = str(n)
	if n > 0 and n < 10:
		print(n)
	else:
		print(9 + int(a[0]) + (len(a) - 2) * 9)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	if n <= 10:
		ans = n
	elif n <= 100:
		ans = 10 + (n // 10 - 1)
	elif n <= 1000:
		ans = 19 + (n // 100 - 1)
	elif n <= 10000:
		ans = 28 + (n // 1000 - 1)
	elif n <= 100000:
		ans = 37 + (n // 10000 - 1)
	elif n <= 1000000:
		ans = 46 + (n // 100000 - 1)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	if n <= 10:
		result = n
	elif n <= 100 and n > 10:
		result = 10 + int(n / 10) - 1
	elif n <= 1000 and n > 100:
		result = 19 + int(n / 100) - 1
	elif n <= 10000 and n > 1000:
		result = 28 + int(n / 1000) - 1
	elif n <= 100000 and n > 10000:
		result = 37 + int(n / 10000) - 1
	elif n <= 1000000 and n > 100000:
		result = 46 + int(n / 100000) - 1
	print(result)


t = int(input())
for k in range(t):
	n = input()
	k = len(n)
	print(int(n[0]) + (k - 2) * 9 + 9)


for i in range(int(input())):
	n = int(input())
	n = str(n)
	l = len(n)
	ans = int(n[0]) + (len(n) - 1) * 9
	print(ans)


t = int(input())
while t:
	n = input()
	if len(n) == 1:
		print(n)
	elif len(n) == 2:
		print(9 + int(n) // 10)
	elif len(n) == 3:
		print(18 + int(n) // 100)
	elif len(n) == 4:
		print(27 + int(n) // 1000)
	elif len(n) == 5:
		print(36 + int(n) // 10000)
	elif len(n) == 6:
		print(45 + int(n) // 100000)
	t -= 1


n = int(input())
for _ in range(n):
	x = int(input())
	if x < 10:
		print(x)
	else:
		s = str(x)
		h = (len(s) - 1) * 9 + int(s[0])
		print(h)


t = int(input())
for tt in range(t):
	n = input()
	count = (len(n) - 1) * 9 + int(n[0])
	print(count)


for _ in range(int(input())):
	s = input()
	l = len(s) - 1
	print(l * 9 + int(s[0]))


def count_extremely_round_int(n):
	count = 0
	while n > 9:
		count += 9
		n = n // 10
	return count + n
t = int(input())
for i in range(t):
	n = int(input())
	print(count_extremely_round_int(n))


def sol():
	n = input()
	l = len(str(n))
	ans = 9 * (l - 1) + int(n[0])
	print(ans)
	return
for i in range(int(input())):
	sol()


import math
t = int(input())
for i in range(t):
	n = input()
	print(int(n[0]) + (len(n) - 1) * 9)


for _ in range(int(input())):
	n = input()
	x = len(n) - 1
	print(9 * x + int(n) // 10 ** x)


for __ in range(int(input())):
	n = input()
	print(int(n[0]) + (len(n) - 1) * 9)


for _ in range(int(input())):
	number = input()
	power = len(number) - 1
	result = int(number) // 10 ** power + power * 9
	print(result)


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n <= 9:
		print(n)
		continue
	print(int(math.log10(n)) * 9 + int(str(n)[0]))


t = int(input())
for _ in range(t):
	n = input()
	super_round_cnt = (len(n) - 1) * 9 + int(n[0])
	print(super_round_cnt)


t = int(input())
for i in range(0, t):
	n = int(input())
	n = str(n)
	size_n = len(n)
	first_ch = n[0]
	diff = int(int(first_ch) - int(0))
	print(diff + 9 * size_n - 9)


x = int(input())
for i in range(0, x):
	y = input()
	x = int(y[0])
	z = len(y)
	if z == 1:
		print(y)
	else:
		z = z - 1
		ans = 9 * z + x
		print(ans)


t = int(input())
for i in range(0, t):
	n = input()
	print(9 * len(n) + int(n[0]) - 9)


t = int(input())
for i in range(t):
	s = input()
	print(int(s[0]) + 9 * (len(s) - 1))


t = int(input())
for _ in range(t):
	x = input()
	res = (len(x) - 1) * 9 + int(x[0])
	print(res)


def super_circ():
	AmmccYy = 0
	AmZx = int(input())
	for i in range(AmZx):
		AmZx1 = str(input())
		AmZ_x = list(AmZx1)
		AmZx1 = int(AmZx1)
		if AmZx1 < 10:
			print(AmZx1)
		else:
			print(int(AmZ_x[0]) + (len(AmZ_x) - 1) * 9)
super_circ()


n = int(input())
for i in range(n):
	s = input()
	x = len(s)
	print((x - 1) * 9 + int(s[0]))


number_of_test_cases = int(input())
for i in range(number_of_test_cases):
	number = int(input())
	if number <= 10:
		print(number)
	else:
		if number <= 100:
			number = number // 10 + 9
		elif number <= 1000:
			number = number // 100 + 18
		elif number <= 10000:
			number = number // 1000 + 27
		elif number <= 100000:
			number = number // 10000 + 36
		else:
			number = number // 100000 + 45
		print(number)


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	answer = 0
	if n > 10:
		answer += 10
	else:
		answer += n
		print(answer)
		continue
	if n > 100:
		answer += 9
	else:
		answer += (n - 10) // 10
		print(answer)
		continue
	if n > 1000:
		answer += 9
	else:
		answer += (n - 100) // 100
		print(answer)
		continue
	if n > 10000:
		answer += 9
	else:
		answer += (n - 1000) // 1000
		print(answer)
		continue
	if n > 100000:
		answer += 9
	else:
		answer += (n - 10000) // 10000
		print(answer)
		continue
	if n > 1000000:
		answer += 9
	else:
		answer += (n - 100000) // 100000
		print(answer)
		continue
	print(answer)


def compute(num):
	n = len(num)
	out = 0
	if n == 1:
		return num
	out += (n - 1) * 9
	out += int(num[0])
	return out
t = int(input())
for i in range(t):
	num = input()
	out = compute(num)
	print(out)


for i in range(int(input())):
	x = input()
	print(ord(x[0]) - ord('0') + (len(x) - 1) * 9)


for _ in range(int(input())):
	n = int(input())
	if n // 10 == 0:
		print(n)
	elif n // 100 == 0:
		print(9 + int(n / 10))
	else:
		l = len(str(n))
		n1 = int(str(n)[0])
		print(n1 + (l - 1) * 9)


t = int(input())
for _ in range(t):
	n = int(input())
	res = 9
	if n < 10:
		print(n)
	elif n < 100:
		print(9 + n // 10)
	elif n < 1000:
		print(9 + 9 + n // 100)
	elif n < 10000:
		print(9 + 9 + 9 + n // 1000)
	elif n < 100000:
		print(9 + 9 + 9 + 9 + n // 10000)
	else:
		print(9 + 9 + 9 + 9 + 9 + n // 100000)


t = int(input())
for i in range(t):
	n = int(input())
	if 1 <= n <= 9:
		print(n)
	elif 10 <= n <= 99:
		print(9 + n // 10)
	elif 100 <= n <= 999:
		print(9 + 9 + n // 100)
	elif 1000 <= n <= 9999:
		print(9 + 9 + 9 + n // 1000)
	elif 10000 <= n <= 99999:
		print(9 * 4 + n // 10000)
	elif 100000 <= n <= 999999:
		print(9 * 5 + n // 100000)


import math
for _ in range(int(input())):
	n = int(input())
	digits = int(math.log10(n))
	print(digits * 9 + int(n / 10 ** digits))


t = int(input())
for i in range(t):
	n = int(input())
	if n < 11:
		print(n)
	elif n > 100 and n <= 1000:
		print(9 + 9 + int(n / 100))
	elif n > 1000 and n <= 10000:
		print(9 + 9 + 9 + int(n / 1000))
	elif n > 10000 and n <= 100000:
		print(9 + 9 + 9 + 9 + int(n / 10000))
	elif n > 100000 and n <= 1000000:
		print(9 + 9 + 9 + 9 + 9 + int(n / 100000))
	elif n > 1000000 and n <= 10000000:
		print(9 + 9 + 9 + 9 + 9 + 9 + int(n / 1000000))
	else:
		print(9 + int(n / 10))


def solution():
	n = int(input())
	num = n
	pow = -1
	while num:
		num //= 10
		pow += 1
	ans = 9 * pow + n // 10 ** pow % 10
	print(ans)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()