Bakhtiar sir's Artificial Intelligence Lab is famous for its exciting 'Pacman' challenges. But some students, unwilling to risk their marks solving the tasks on the spot, have been secretly studying previous years' solutions passed down by seniors. However, this time Bakhtiar sir outsmarted them by introducing a brand new lab task — a twist on the classic Pacman game where the ghosts are replaced by Vampires.
The game proceeds in turns. In each turn, Pacman moves first, and then the vampires move one by one. Pacman will eat the food pellet immediately after reaching it. The game ends as soon as Pacman eats the food pellet and exits the game, or after $$$10^7$$$ turns.
The input of the task is a two-dimensional grid world containing:
- Walkable empty spaces (.)
- Impassable walls (#)
- The starting position of Pacman (P)
- One food pellet (F)
- Vampires (V)
The moves available to Pacman are:
- U (Up): Pacman moves one cell up if the cell above is within the grid and not a wall. Otherwise, Pacman stays in place.
- D (Down): Pacman moves one cell down if the cell below is within the grid and not a wall. Otherwise, Pacman stays in place.
- L (Left): Pacman moves one cell to the left if the cell to the left is within the grid and not a wall. Otherwise, Pacman stays in place.
- R (Right): Pacman moves one cell to the right if the cell to the right is within the grid and not a wall. Otherwise, Pacman stays in place.
- S (Stay): Pacman remains in the current cell.
- E (Exit): Ends the game immediately if Pacman has already eaten the food pellet. Otherwise, Pacman stays in place.
The moves available to each Vampire are:
- U (Up): Vampire moves one cell up if the cell above is within the grid and not a wall. Otherwise, Vampire stays in place.
- D (Down): Vampire moves one cell down if the cell below is within the grid and not a wall. Otherwise, Vampire stays in place.
- L (Left): Vampire moves one cell to the left if the cell to the left is within the grid and not a wall. Otherwise, Vampire stays in place.
- R (Right): Vampire moves one cell to the right if the cell to the right is within the grid and not a wall. Otherwise, Vampire stays in place.
- S (Stay): Vampire remains in the current cell.
After the end of any turn, if a Vampire that hasn't bitten Pacman yet is in the same cell as Pacman, it will bite it. Each Vampire can bite Pacman at most once, but multiple Vampires can bite Pacman after the same turn.
The output of the lab task is a sequence of moves for Pacman. After a student submits his move sequence, Bakhtiar sir's AI will read it and control the Vampires optimally to maximize the number of Vampires that can bite Pacman before the game ends.
Pacman gets +500 points for eating the food pellet. However, each time a Vampire bites Pacman, -10 points is added to the score (Pacman loses 10 points). The final score can be negative.
To obtain full marks in the lab, a student must submit a move sequence that maximizes the final score, despite the Vampires moving optimally.
Tanbir, surprised by this new task, wants to solve it carefully. Before actually finding a move sequence, he wants to know the maximum score that is theoretically achievable for a given grid and initial position of Pacman and vampires. Your task is to calculate this.
The first line of the input contains an integer $$$t$$$ $$$(1 \le t \le 1000)$$$ — the number of test cases.
The first line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 10^6)$$$ — the number of rows and columns in the grid world.
The next $$$n$$$ lines contain a string of length $$$m$$$ — describing the grid world layout.
Each character in the grid is one of the following
- '.': represents an empty space
- '#': represents a wall
- 'P': represents Pacman's starting position
- 'F': represents the food pellet
- 'V': represents a Vampire
It is guaranteed that the grid for each test case contains exactly one 'P' and exactly one 'F', and the sum of $$$n \times m$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print a single integer in a line — the maximum score achievable.
84 8P......V.....F....V.............4 8PV.........V....F.........V.....4 8PV......#..V....F.........V.....5 6P...#...#..#.V.#.F.#..#.V.....3 2#VPF#V1 12P..V.V...V.F3 12P#...#...#.F.#.#.#.#.#.#...#...#...#8 8PVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVF
480 500 470 490 480 470 500 -120
The first test case is illustrated in the following diagram:
Here, one of the optimal move sequences for Pacman is "RDRRRRE". The vampire in the first row (from the top) can meet Pacman with the move sequence "LLLDXX". The vampire in the third row can meet Pacman with the move sequence "LUXXXX". Here, 'X' means any move.
The layouts of all other sample test cases are illustrated below:
 |  |  |
 |  |
 |  |
