#P9354. 「SiR-1」Popsicle

「SiR-1」Popsicle

题目背景

猫猫喜欢收集雪糕棒,每十三个捆成一束。

可爱的猫猫喜欢优雅地摆烂。

题目描述

猫猫有若干个雪糕棒排成一排,每个雪糕棒上有一个 090\sim 9 的数字,并且满足最左边的雪糕棒上写的数字不为 00。猫猫认为这一排雪糕棒从左到右依次构成了十进制正整数 nn

猫猫认为 00 是美好的,所以她会尽可能把 nn 变成 00,也就是把所有雪糕棒都拿走。

猫猫每次会进行一次操作。每次操作选择一个数字非 00 的雪糕棒,并将其减 11。这之后,如果最左边有连续的一些数字为 00 的雪糕棒(也即 nn 出现了前导 00),猫猫会把这些雪糕棒拿走。

小老鼠会来捣乱,它会在某个时刻(可能是所有操作开始之前,也可能是猫猫任意一次操作之后)改变某个雪糕棒上的一个数字。小老鼠总共只能改变一个数字

小老鼠希望操作次数尽量多,猫猫希望操作次数尽量少,所以她想知道二者都使用最优策略时,她的操作次数。

输入格式

本题有多组数据。

第一行一个正整数 TT 表示数据组数。

对于每组数据:仅一行,一个正整数 nn

输出格式

TT 行,每行一个整数,表示答案。

2
1100
11332132121
11
28

提示

样例解释 1

对于第一组数据,小老鼠可以一开始就将 11001100 变为 11091109,这样猫猫共需要 1+1+91 + 1 + 9 次操作把 nn 变为 00

数据规模与约定

  • Subtask 0(13 pts):n99n \leq 99
  • Subtask 1(13 pts):n=10kn = 10^kkk 为自然数。
  • Subtask 2(13 pts):n=10k1n = 10^k - 1kk 为正整数。
  • Subtask 3(13 pts):n999 999n \leq 999\ 999
  • Subtask 4(48 pts):无特殊限制。

对于所有数据,1T33331 \leq T \leq 33331n9 999 999 999 999(=10131)1 \leq n \leq 9\ 999\ 999\ 999\ 999(=10^{13} - 1),毕竟猫猫最多一捆只有 1313 根雪糕嘛。