← 返回题目列表

Codeforces · 1567/C

C. 携带难题

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

Alice 刚刚学会了加法。然而,她还没有完全学会“进位”的概念——她不是进位到下一列,而是进位到左边两列。

例如,计算总和 $$$2039 + 2976$$$ 的常规方法如下所示:

然而,Alice 对其进行评估,如下所示:

特别是,她这样做:

- 将 $$$9$$$ 和 $$$6$$$ 添加到 $$$15$$$,并将 $$$1$$$ 移至左侧两列,即。 e.到“$$$0$$$ $$$9$$$”列;
- 将 $$$3$$$ 和 $$$7$$$ 添加到 $$$10$$$ 并将 $$$1$$$ 移至左侧两列,即。 e.到“$$$2$$$ $$$2$$$”列;
- 将 $$$1$$$、$$$0$$$ 和 $$$9$$$ 添加到 $$$10$$$ 并将 $$$1$$$ 移至左侧两列,i。 e.到加号上方的列;
- 添加 $$$1$$$、$$$2$$$ 和 $$$2$$$ 得到 $$$5$$$;
- 添加 $$$1$$$ 使 $$$1$$$。

Alice 走到 Bob 面前,说她已经将两个数字相加,得到的结果是 $$$n$$$。然而,鲍勃知道爱丽丝以她自己的方式添加。帮助 Bob 找到正整数的有序对的数量,这样当 Alice 将它们相加时,她将得到 $$$n$$$ 的结果。请注意,如果 $$$a \ne b$$$,则 $$$(a, b)$$$ 和 $$$(b, a)$$$ 被视为不同。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^9$$$) - Alice 向 Bob 展示的数字。

输出

对于每个测试用例,输出一个整数 - 有序正整数对的数量,这样当 Alice 将它们相加时,她将得到 $$$n$$$ 结果。

示例

输入 #1

5
100
12
8
2021
10000

输出 #1

9
4
7
44
99

注意

在第一个测试用例中,当 Alice 计算 $$$1 + 9$$$、$$$2 + 8$$$、$$$3 + 7$$$、$$$4 + 6$$$、$$$5 + 5$$$、$$$6 + 4$$$、$$$7 + 3$$$、$$$8 + 2$$$ 中的任何一个时,或者$$$9 + 1$$$,她将得到$$$100$$$的结果。下图展示了Alice如何评估$$$6 + 4$$$: