Automatic Tetris Player

A random sequence of tetrominoes (sometimes called "tetrads" in older versions)-shapes composed of four square blocks each-fall down the playing field (a rectangular vertical shaft, called the "well" or "matrix"). The object of the game is to manipulate these tetrominoes, by moving each one sideways and rotating it by 90 degree units, with the aim of creating a horizontal line of blocks without gaps. When such a line is created, it disappears, and any block above the deleted line will fall. As the game progresses, the tetrominoes fall faster, and the game ends when the stack of tetrominoes reaches the top of the playing field and no new tetrominoes are able to enter.

-- Wikipedia (http://en.wikipedia.org/wiki/Tetris)

Task
The seven one-sided tetrominoes below are represented by I, J, L, O, S, T, Z from first row to the second, left to right. Look at their shapes, then you'll realize why they're called this way.

Your task is to implement an automatic tetris player. You'll be given a sequence of blocks, and your objective is to minimize the sum of squares of column heights. By "height", we mean the row number of the topmost non-empty unit block of that column. Rows are numbered 1, 2, 3, ..., in a bottom-up order. Technically, if we denote the height of column i by hi, you should minimize sum{(hi)²}.

For simplicity, assume each block is falling from high enough, and you cannot control the block anymore, once you decide its rotating and horizontal position. Note that you cannot mirror the blocks, only horizontal moving and rotating is permitted.

The field is always 5 columns wide. When a line of unit blocks are eliminated, the vertical position of everything above the line is decreased by 1. This is the most widely used algorithm. But the resulting board may looks strange, since things can "float up in the sky", see below.

The first line contains a single integer T (T <= 20), the number of test cases. Each case contains a single line of a string, representing the block sequence. There will be no more than 5 blocks, each of them will be one of I, J, L, O, S, T and Z.

For each test case, print the case number and the minimal possible score.

3
LLLLO
IJ
STZ

Case 1: 0
Case 2: 3
Case 3: 15

2009 Asia Regional Ningbo Online