#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int INF = 1<<30;int block[][4][2] = { {1, 1, 1, 2, 1, 3, 1, 4}, {1, 1, 2, 1, 2, 2, 2, 3}, {1, 3, 2, 1, 2, 2, 2, 3}, {1, 1, 1, 2, 2, 1, 2, 2}, {1, 2, 1, 3, 2, 1, 2, 2}, {1, 2, 2, 1, 2, 2, 2, 3}, {1, 1, 1, 2, 2, 2, 2, 3} };int rotime[] = {2, 4, 4, 1, 2, 4, 2};int robase[][2] = {1, 1, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 1, 2};int n, ans;char s[30];void dfs(int cur, int mp[][6]){ int mp1[30][6]; int hight[6]; memset(hight, 0, sizeof(hight)); memcpy(mp1, mp, sizeof(int) * 6 * 30); for(int i = 1; ; i++){ bool hasone = false, noone = false; for(int j = 1; j <= 5; j++){ if(mp1[i][j]){ hasone = true; }else noone = true; } if(!hasone) break; if(!noone){ for(int k = i; ;){ for(int j = 1; j <= 5; j++){ mp1[k][j] = mp1[k + 1][j]; mp1[k + 1][j] = 0; } k++; hasone = false; for(int j = 1; j <= 5; j++){ if(mp1[k + 1][j]){ hasone = true; } } if(!hasone) break; } i--; } } for(int i = 1; ; i++){ bool hasone = false; for(int j = 1; j <= 5; j++){ if(mp1[i][j]){ hight[j] = i; hasone = true; } } if(!hasone) break; } int tans = 0; for(int i = 1; i <= 5; i++){ tans += hight[i] * hight[i]; } if(cur == n){ ans = min(ans, tans); return ; } int coor[4][2], tmp[4][2]; int maxj, minj; int dex = s[cur] - '0'; for(int i = 0; i < 4; i++){ coor[i][0] = block[dex][i][0]; coor[i][1] = block[dex][i][1]; } memcpy(tmp, coor, sizeof(coor)); for(int i = 0; i < rotime[dex]; i++){ maxj = 0; minj = INF; if(i){ for(int j = 0; j < 4; j++){ coor[j][0] = (tmp[j][1] - robase[dex][1]) + robase[dex][0]; coor[j][1] = -(tmp[j][0] - robase[dex][0]) + robase[dex][1]; maxj = max(maxj, coor[j][1]); minj = min(minj, coor[j][1]); } memcpy(tmp, coor, sizeof(coor)); if(minj != 1){ for(int j = 0; j < 4; j++){ coor[j][1] -= (minj - 1); } maxj -= (minj - 1); } }else{ for(int j = 0; j < 4; j++) maxj = max(maxj, coor[j][1]); } for(int j = 0; j + maxj <= 5; j++){ for(int k = 0; k < 4; k++){ coor[k][1] += j; } int d = INF; for(int k = 0; k < 4; k++){ d = min(d, (30 - coor[k][0]) - hight[coor[k][1]] - 1); } for(int k = 0; k < 4; k++){ mp1[30 - coor[k][0] - d][coor[k][1]] = cur + 1; } dfs(cur + 1, mp1); for(int k = 0; k < 4; k++){ mp1[30 - coor[k][0] - d][coor[k][1]] = 0; } for(int k = 0; k < 4; k++){ coor[k][1] -= j; } } }}int main(){ int t; int mp[30][6]; scanf("%d", &t); for(int i = 1; i <= t; i++){ scanf("%s", s); n = strlen(s); for(int j = 0; j < n; j++){ if(s[j] == 'I'){ s[j] = '0'; }else if(s[j] == 'J'){ s[j] = '1'; }else if(s[j] == 'L'){ s[j] = '2'; }else if(s[j] == 'O'){ s[j] = '3'; }else if(s[j] == 'S'){ s[j] = '4'; }else if(s[j] == 'T'){ s[j] = '5'; }else if(s[j] == 'Z'){ s[j] = '6'; } } memset(mp, 0, sizeof(mp)); ans = INF; dfs(0, mp); printf("Case %d: %dn", i, ans); } return 0;}
