Sanjay and his friends are searching for treasure in an abandoned castle. They have just entered the castle and find themselves faced with a maze of treasure-filled rooms separated by locked doors. Fortunately for them, the old owners left spare keys littered around the castle.

Sanjay finds that they can use any key to help open any door in the castle. However, some doors require multiple keys in order to open them.

The floor plan of the castle can be represented as an ~N \times N~ grid of the following characters:

• . denotes an empty space.
• # denotes a wall.
• Characters 1 through 9 denote a door, with the number representing how many keys it takes to open the door.
• K represents a key.
• T represents a treasure.
• S represents Sanjay's start point.

Input Specification

The input will contain ~10~ test cases. Each test case starts with an integer ~N~ ~(1 \le N \le 1000)~. The next ~N~ lines each contain ~N~ characters denoting the floor plan of the castle.

Output Specification

For each test case, your program should output the number of treasures that Sanjay and his friends will be able to retrieve.

Sample Input

3
.SK
#1#
T..
5
S.2.T
.K##3
11##T
....#
..T.K

Sample Output

1
2

Note: Only ~2~ cases are shown in this sample.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org