Problem Statement

A Positive number n will be called special if all the digits of the number are the same. For example, 4,5 & 11 are special numbers but 123,2019 are not special numbers.

For a given number n, find the number of special numbers from 1 to n. Both 1 and n are inclusive

Input

The first line contains one integer t (1≤t≤10⁴). Then t test cases follow.

Each test case is characterized by one integer n (1≤n≤10⁹).

Output

For each test case output the number of special numbers from 1 to n. Both 1 and n are inclusive.