Codeforces Round 905 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Morning

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a four-digit pin code consisting of digits from $$$0$$$ to $$$9$$$ that needs to be entered. Initially, the cursor points to the digit $$$1$$$. In one second, you can perform exactly one of the following two actions:

- Press the cursor to display the current digit,
- Move the cursor to any adjacent digit.

The image above shows the device you are using to enter the pin code. For example, for the digit $$$5$$$, the adjacent digits are $$$4$$$ and $$$6$$$, and for the digit $$$0$$$, there is only one adjacent digit, $$$9$$$.

Determine the minimum number of seconds required to enter the given four-digit pin code.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) - the number of the test cases. This is followed by their description.

The single line of each test case describes the pin code as a string of length $$$4$$$, consisting of digits from $$$0$$$ to $$$9$$$.

Output

For each test case, output the minimum number of seconds required to enter the given pin code.

Example

Input

101111123610101920927300007492854302948361

Output

4 9 31 27 28 13 25 16 33 24

Note

In the first test case, the cursor needs to be pressed $$$4$$$ times.

In the second test case, it can be done in $$$9$$$ seconds as follows:

- Press the cursor.
- Move the cursor to the digit $$$2$$$.
- Press the cursor.
- Move the cursor to the digit $$$3$$$.
- Press the cursor.
- Move the cursor to the digit $$$4$$$.
- Move the cursor to the digit $$$5$$$.
- Move the cursor to the digit $$$6$$$.
- Press the cursor.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 08:43:20 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|