FOC has designed a new Music Instrument for Varchas Pronite. The board is divided ( 4 * 3) into small square shape cells. The shape of the board is rectangular. FOC team has decided to play some songs on that board. A song consist of many chords(omega,beta,theta).
To play some chord ,you have to place your fingers on the cells of the board at certain positions.
For Example :
0010 means you need not to put any finger on 1st , second and fourth row and you have to put one finger in the third row first column. There are 3 type of placement of fingers which are universally known. These are named as omega,beta,theta(chords).
omega="2330"
beta="0212"
theta="0111"
You have to minimize the distance travelled by your fingers in one complete song. Distance is defined as the following. (You can only slide fingers) Suppose your one finger is at 2nd row 2nd column and you want to move your finger to same row 7th column. Then total distance travelled by that finger = 5. And if you want to move finger to 3rd row 3rd column from 2nd row 2d column then total distance travelled by that finger = 2 ( one down and one right) So if you have placed your fingers in omega configuration and you want to change your position to beta you need to move your figures 6 distance total.
A song consist combinations of omega, beta and theta only. So you are required to find minimum distance traveled by the fingers during one song.
Note:
Initially your fingers are at 0000 position.
You can use only 3 fingers to play the songs.
You can use only one hand.
You can ignore the distance travelled by the fingers for first chord
Maximum Number of chords in the songs = 10^5
Input
First line consist of number of Songs(N).
Next N lines consist of space separated chords of the song.
Number of Songs <=10
Output
N lines.
ith line is equal to minimum number of distance traveled by the fingers for ith song.