题目描述

翁老师在给学生们出题时，构思了一个奇特的虚拟星系历法。在这个历法系统中，一整年被划分为了 $n$ 个月份。每个月的天数并不是固定的，具体来说，第 $i$ 个月恰好包含 $10^{a_i}-1$ 天。

接着，翁老师定义了一个叫做“对称纪念日”的概念。如果在某一天，我们将当前的月份数字 $m$ 与日期数字 $d$ 直接按顺序拼接起来（构成一个新的数字序列 $\overline{md}$），发现它从左往右读和从右往左读完全相同，那么这一天就属于“对称纪念日”。

• 打个比方，$12$ 月 $21$ 日算作对称纪念日，因为拼接出的 $1221$ 左右对称；而 $10$ 月 $3$ 日就不算，因为拼接出的 $103$ 并不对称。

翁老师希望你编写一个程序，帮忙统计出在这个虚拟历法之下，一整年里究竟会包含多少个这样的“对称纪念日”。

输入格式

本题包含多组测试数据。

首行输入两个非负整数 $T$ 和 $c$，分别代表测试数据的总组数以及当前测试点所属的子任务编号。需要特别留意的是，如果 $c=0$，则说明当前正在测试的是样例数据。

接下来依次提供 $T$ 组测试的具体数据。对于每组测试数据：

• 第一行包含一个正整数 $n$。
• 第二行包含 $n$ 个非负整数，依次为 $a_1,a_2,\dots,a_n$。

输出格式

对于每一组测试数据，请单独输出一行一个整数，代表在翁老师设定的这一年里总共出现的“对称纪念日”的数量。

1 0
20
2 1 5 4 3 5 2 4 3 5 2 4 2 5 3 1 4 3 5 2

1072

提示

样例 1 解释

在样例设定的年份中共有 $20$ 个月。

• $1$ 月共有 $99$ 天，其中包含 $10$ 个对称纪念日，分别是 $1$ 月 $1$ 日、$1$ 月 $11$ 日、$1$ 月 $21$ 日等等。
• $2$ 月共有 $9$ 天，只有 $1$ 个对称纪念日，也就是 $2$ 月 $2$ 日。
• $11$ 月共有 $99$ 天，包含 $2$ 个对称纪念日，即 $11$ 月 $1$ 日和 $11$ 月 $11$ 日。
• $15$ 月共有 $999$ 天，包含了 $11$ 个对称纪念日，分别是 $15$ 月 $1$ 日、$15$ 月 $51$ 日、$15$ 月 $151$ 日等等。

数据范围

本题目采用 子任务捆绑测试 与 子任务依赖 机制。选手需要通过某个子任务内的所有测试点，并且通过该子任务所依赖的其他前置子任务，才能拿到对应的分数。

• Subtask $0$（$0$ pts）：样例测试点。
• Subtask $1$（$40$ pts）：保证 $10^{a_1}+10^{a_2}+\dots+10^{a_n} \le 10^6$。依赖于 Subtask 0。
• Subtask $2$（$20$ pts）：保证 $10^{a_i}-1 \le i$。
• Subtask $3$（$20$ pts）：保证 $n \le 9$。
• Subtask $4$（$20$ pts）：无特殊限制。依赖于 Subtask $0 \sim 3$。

对于所有的测试数据，保证满足：$1 \le T \le 5$，$0 \le c \le 4$，$1 \le n \le 10^5$，$0 \le a_i \le 10$。