题目描述

小 Y 有一块很大很大的苹果林。在收获的季节，有一个小偷想去偷苹果被发现了。小偷很强壮，所以小 Y 不能把小偷赶走，但是小偷也不愿意伤害小 Y ，因为他只想要苹果。

怎么让小偷得到尽量少的苹果呢？小 Y 决定抢在小偷之前把苹果摘走。我们可以认为小 Y 和小偷都是超高智商的，你的任务是计算小偷最多能够偷走多少苹果。

我们认为苹果林是一个 $5\times 6$ 的矩阵，矩阵只有 $3$ 种元素 : 空地，苹果树和障碍物。我们保证苹果树有且只有 $4$ 棵，每棵苹果树有且只有 $3$ 个苹果，小 Y 和小偷可以停留在空地或者是苹果树的位置上，但是他们不能够停留在障碍物上（你可以认为那里是一个臭水沟）。

苹果争夺战小偷先移动，然后是小 Y 。两人轮流移动，直到没有苹果可以摘了。

摘苹果有两个规则 :

• 当一个人到达一个有苹果的苹果树的方格中，他可以立刻得到一个苹果。
• 移动时一个人可以选择停留在苹果树的方格上去摘苹果（如果还有苹果他将得到一个）。

每次移动时，一个人可以从 $(x,y)$ 移动到 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ ，但是移动去的方格不能是墙、矩阵外或者是另一个人停留的位置；当然，如果满足以下两种情况，他也可以停留在原地 :

• 他停留在一个苹果树方格上，不管这棵苹果树上是否有苹果。
• 他不能移动到周围任何一个方格中。

输入格式

本题有多组输入。

第一行有一个正整数 $T$，表示数据组数，然后是 $T$ 组数据。

每组数据由 $5$ 行组成，每行有 $6$ 个字符，使用 $5$ 中字符描述矩阵：.、#、3、S、T。

• . 表示空地
• # 表示障碍物
• 3 表示苹果树
• S 表示小 Y
• T 表示小偷

每组数据有且只有 $1$ 个 S 和 T，并且其所在的位置一定是一个空地。每组数据至少有一半的位置是障碍物，每组数据的最后都有一个空行。

输出格式

每组数据输出一个整数表示小偷最多能够得到的苹果数

3 
T3333.
#####S
######
######
######

####..
.3.3..
33.T.S
######
######

##3###
##.##3
TS3###
##.###
##3###

9
12
0

样例说明

对于第三个样例，小 Y 可以永远停留在他右边的苹果树上，那么小偷就再也偷不到苹果了，此时 Game Over。

数据范围

对于 $100\%$ 的数据：$T \leq 20$。

题目来源

Acm2005 成都