Laurel Creek

Laurel Creek is a dangerous river that splits the campus in two and is home to hazards such as geese and beavers. Your task is to find a way across the river without getting wet.

To cross, you use several tree stumps standing in the river. A stump is a safe place to stand while you plan your next move, and you travel from one stump to another by walking along the logs that connect them.

If no log connects to the stump you want to reach, you are not stuck: you may pick up a log that is adjacent to the stump you are standing on and set it down elsewhere so that it reaches the stump you want. A log counts as adjacent to a stump only when it is oriented correctly. For example, the log in S-S is adjacent to both stumps, but the log in S|S is adjacent to neither stump.

Every stump sits at a point of a square grid. Two stumps are designated as the start and the end of the crossing. Any two stumps in the same row or the same column may be joined by a log. At any moment you may make exactly one of the following legal moves:

• Traverse a log that is adjacent to the stump you are standing on, moving to the stump at the far end of that log.
• Pick up a log that is adjacent to the stump you are standing on. You may never hold more than one log at a time.
• Put down the log you are holding so that it connects the stump you are standing on to another stump. The log must be exactly the right length to reach that stump. The log must rest on the water: you may not join two stumps if a third stump lies directly between them, or if the log would cross another log already lying in the water.

The first line contains one integer, the number of test cases. Each test case starts with a line containing two integers $r$ and $c$ with $1 \le r \le 15$ and $1 \le c \le 15$, the numbers of rows and columns of the grid. Each of the next $r$ lines contains $c$ characters with the following meaning: S is a stump; B and E are the start and end stumps of the crossing; a consecutive run of - or | characters is a single log whose length is proportional to the number of symbols; and . is an empty grid point holding only water. The river never contains more than fifteen stumps.

For each test case, output one line with a single integer: the minimum number of moves needed to reach the end stump from the initial configuration, where one move is any one of the three legal moves above (traverse, pick up, or put down). If the end stump cannot be reached, output 0.