D. Professor Oak Strikes Back
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Professor Oak is typing a text on his computer and, as usual, he uses only his two index fingers. The text consists solely of uppercase letters without accents, the characters ",", ".", ":", ";", "'", "?", "!", and spaces and line breaks. All characters, except for spaces and line breaks, have an associated key, which is shown in the keyboard layout below.

Professor Oak starts typing with his left index finger on the F key and his right index finger on the J key. At any moment, he can move either of his fingers to one of the four adjacent keys (or three or two if he is at the edge of the keyboard) and it takes him one second to make this movement. Additionally, he is capable of moving both fingers simultaneously. His prodigious skill also allows him to press a key instantly (i.e., in zero seconds) if one of his two index fingers is on it. The space bar and the ENTER key, which correspond to spaces and line breaks, are very large, so Professor Oak presses them with the tip of his nose, also instantly.

Given the text that Professor Oak has written, determine the time it took him to write it, knowing that he does so optimally. You can assume that Professor Oak has infinitely flexible arms, meaning he can intertwine them without any problem.

Input

The input begins with an integer $$$t \geq 1$$$, the number of cases. Each case consists of a text, which consists of uppercase letters without accents, the characters ",", ".", ":", ";", "'", "?", "!", and spaces and line breaks. The end of the text will be indicated by the character "-". The cases are separated by a line break.

Output

Print a single integer: the time that Professor Oak took to write the text.

Scoring

In all inputs, $$$1 \leq t \leq 10$$$.

5 Points:     The text contains only the characters 'F', 'J', spaces, and line breaks and does not exceed 1000 characters in total.

10 Points:    The text contains only two characters that are not spaces or line breaks and does not exceed 1000 characters in total.

35 Points:    The text does not exceed 16 characters.

50 Points:     The text does not exceed 1000 characters.

Examples
Input
1
FJ RU EI WO QP-
Output
4
Input
1
HELLO THERE! WELCOME TO THE WORLD OF POKEMON! MY NAME IS OAK. PEOPLE CALL ME THE POKEMON PROF. THIS WORLD IS INHABITED BY CREATURES CALLED POKEMON. FOR SOME PEOPLE, POKEMON ARE PETS. OTHERS USE THEM FOR FIGHTS. MYSELF... I STUDY POKEMON AS A PROFESSION.
-
Output
295
Input
1
PALPATINE: DID YOU EVER HEAR THE TRAGEDY OF DARTH PLAGUEIS THE WISE?

ANAKIN: NO.

PALPATINE: I THOUGHT NOT. IT'S NOT A STORY THE JEDI WOULD TELL YOU. IT'S A SITH LEGEND. DARTH PLAGUEIS WAS A DARK LORD OF THE SITH, SO POWERFUL AND SO WISE HE COULD USE THE FORCE TO INFLUENCE THE MIDICHLORIANS TO CREATE LIFE... HE HAD SUCH A KNOWLEDGE OF THE DARK SIDE, HE COULD EVEN KEEP THE ONES HE CARED ABOUT FROM DYING.

ANAKIN: COULD HE ACTUALLY SAVE PEOPLE FROM DEATH?

PALPATINE: THE DARK SIDE OF THE FORCE IS A PATHWAY TO MANY ABILITIES SOME CONSIDER TO BE UNNATURAL.

ANAKIN: WHAT HAPPENED TO HIM?

PALPATINE: HE BECAME SO POWERFUL... THE ONLY THING HE WAS AFRAID OF WAS LOSING HIS POWER, WHICH EVENTUALLY, OF COURSE, HE DID. UNFORTUNATELY, HE TAUGHT HIS APPRENTICE EVERYTHING HE KNEW, THEN HIS APPRENTICE KILLED HIM IN HIS SLEEP. IRONIC. HE COULD SAVE OTHERS FROM DEATH, BUT NOT HIMSELF.

ANAKIN: IS IT POSSIBLE TO LEARN THIS POWER?

PALPATINE: NOT FROM A JEDI.
-
Output
1126