escape-1

We need to escape from a maze in at most S steps. The maze contains: 0-marked freely passable cells. ^v<>-marked free cells - for these, we can only enter from a specific direction: only from below,above,from the right,from the left respectively. But we can exit in any direction (following the rules). 1-marked forbidden cells: cannot step on them, cannot start from them In one move, we can step to a horizontally or vertically adjacent free cell. If we reach the edge of the maze, we have escaped… Determine how many internal (not on the edges) free cells ($E$) exist such that starting from there, we can escape within $S$ steps.

Input specification

The first line contains $T$, the number of mazes. Description of a maze: First line: three numbers $S~~ R~~ C~~$ (maximum steps, rows, columns). Then $R$ lines follow: each containing a string of length $C$ with the characters described above.

Output specification

$T$ lines, each containing the requested number $E$.

Constraints

$1\le T \le 15$
$1\le S \le 200$
$3\le R \le 100$
$3\le C \le 100$

Sample input 1

1. 5
2. 2 4 4
3. 1111
4. 1001
5. 1011
6. 0v11
7. 2 4 4
8. 1111
9. 1001
10. 1011
11. 0>11
12. 1 4 4
13. 1001
14. 1001
15. 1011
16. 0v11
17. 3 5 5
18. 00100
19. 00^00
20. 1<0>1
21. 00v00
22. 00100
23. 6 5 5
24. 00100
25. 00^00
26. 1<0>1
27. 00v00
28. 00100

Sample output 1

1. 2
2. 0
3. 3
4. 9
5. 9