← 返回题目列表

Codeforces · 2104/F

F. 数字和字符串

中文机器翻译题面 查看原题

对于从 $$$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)$$$ 之间不同字符串的数量。

示例

输入
复制

2
42
1337

输出
复制

42
948