CF2104F Numbers and Strings

For each integer $ x $ from $ 1 $ to $ n $ , we will form the string $ S(x) $ according to the following rules: - compute $ (x+1) $ ; - write $ x $ and $ x+1 $ next to each other in the decimal system without separators and leading zeros; - in the resulting string, sort all digits in non-decreasing order. For example, the string $ S(139) $ is 011349 (before sorting the digits, it is 139140). The string $ S(99) $ is 00199. Your task is to count the number of distinct strings among $ S(1), S(2), \dots, S(n) $ .

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of one line containing a single integer $ n $ ( $ 1 \le n \le 10^{9} - 2 $ ).

For each test case, output a single integer — the number of distinct strings among $ S(1), S(2), \dots, S(n) $ .