题目描述

你有 $t$ 个四位数密码，每次输入时你的光标在第一个数 $1$ 上，在一秒内你有两种操作：

• 按下光标输入一位密码。
• 将光标移到任意与当前数字相邻的数字。

这张图显示了你输入密码的设备，可以看到，$5$ 相邻的是 $4$ 和 $6$，而 $0$ 和 $1$ 只有一个相邻的数，分别是 $9$ 和 $2$。

计算输入给定密码需要的最少秒数。

输入格式

第一行输入一个整数 $t$ ($1 \le t \le 10^4$)，表示有几个密码。

接着每行输入一个四位字符串，共 $t$ 行，表示密码，由 $0$ 到 $9$ 组成。

输出格式

共 $t$ 行，每行一个正整数，表示输入给定密码需要的最少秒数。

样例

10
1111
1236
1010
1920
9273
0000
7492
8543
0294
8361

4
9
31
27
28
13
25
16
33
24