Remorse

This problem was used in the following GFU competitions:

• GFU 2024 D2 Q12

• GFU 2024 D1 Q3

A Morse-like code is an assignment of sequences of dots and dashes to alphabet characters. You are to create a Morse-like code that yields the shortest total length to a given message, and return that total length.

A dot has length 1. A dash has length 3. The gap between dots and dashes within a character has length 1. The gap between characters has length three. Spaces, punctuation, and alphabetic case are ignored.

For example, the text

The quick brown dog jumps over the lazy fox.

is encoded as though it were just

THEQUICKBROWNDOGJUMPSOVERTHELAZYFOX

For example, with input CSIS, the answer is 17: Encode the S’s with a single dot, the C with a dash, and the I with two dots, for a total of ‘- . .. .’ which has length 3+3+1+3+1+1+1+3+1 or 17.

The first input is a single integer n that indicates the number of data sets that follow. For each data set, the input will be a single line consisting of uppercase or lowercase letters, spaces, commas, periods, exclamation points, and question marks. The line will have a maximum length of 32,000 characters and will contain at least one letter. Everything but the letters should be ignored.

For each data set, output the length of the encoded string when an optimal Morse-like code is used.