对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$x$$$,我们将根据以下规则形成字符串 $$$S(x)$$$:
- 计算 $$$(x+1)$$$;
- 在十进制系统中将 $$$x$$$ 和 $$$x+1$$$ 彼此相邻写入,不带分隔符和前导零;
- 在结果字符串中,按非降序对所有数字进行排序。
例如,字符串 $$$S(139)$$$ 是 011349 (在对数字进行排序之前,它是 139140)。字符串 $$$S(99)$$$ 是 00199.
你的任务是计算 $$$S(1), S(2), \dots, S(n)$$$ 之间不同字符串的数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含单个整数 $$$n$$$ ($$$1 \le n \le 10^{9} - 2$$$)。
输出
对于每个测试用例,输出一个整数 - $$$S(1)、S(2)、\dots、S(n)$$$ 之间不同字符串的数量。
示例
输入复制
2421337
输出复制
42 948