There are $M$ levels for a building numbered from $1$ to $M$ from top to bottom, each level having $N$ parking spots numbered from $1$ to $N$ from left to right. Some spots might have a car while other may be empty, the information of which is given in form of two dimensional character array $C$ ($C_{i, j}$ denote parking spot at $j$-th position on $i$-th level).
There is a thief who wants to unlock all the cars. Now, he is skilled such that for the first time, he can directly reach in any parking spot in no time. Basically he can reach the first car to be stolen in 0 time.
Now, he can move within the parking lot only in following manner, each taking 1 unit of time:
- Move down a level. That is, if current position is $(i, j)$, then he reaches $(i+1, j)$
- If current position is $(i, j)$ and if
- $i$ is odd, then he can move from $(i, j)$ to $(i, j+1)$
- $i$ is even, then he can move from $(i, j)$ to $(i, j-1)$
Note that he wants to unlock the cars in minimum time and the car is unlocked as soon as the thief reaches that parking spot.If the parking lot is empty, then the time taken is considered to be 0.  
Find the minimum time when all the cars would be unlocked. Note that once all cars are unlocked, the thief can escape instantly, so this time does not count.

-----Input :-----
- The first line of input contains a single integer $T$ (number of test cases).
- First liine of each test case contains $M$ and $N$(number of levels and spots per each level)  
- Next $M$ line contains $N$ space separated characters $C_{i, 1}, C_{i, 2} \ldots C_{i, N}$  where $(1\leq i\leq M)$ and $C_{i, j}$ is either $'P'$ or $'N'$ (without quotes).
If the spot contains $'P'$, then a car is parked there. else, it’s not parked.

-----Output :-----
For each test case print a single integer, the minimum time in which thief can unlock all cars.

-----Constraints :-----
- $1\leq T \leq100.$ 
- $1\leq M,N \leq300$ 

-----Subtasks :-----
- 
Subtask 1 (20 points): $1\leq M \leq2.$ 
- 
Subtask 2 (80 points): Original Constraints

-----Sample Input :-----
2
4 5
N P N N P
N N P N N
N P N N N
P N N N N
3 3
N P P
P P P 
P P N

-----Sample Output :-----
10
6

-----Explanation:-----
In the first case, He will select the spot $(1,2)$ and the path he takes will be $(1,2)→(1,3)→(1,4)→(1,5)→(2,5)→(2,4)→(2,3)→(2,2)→(3,2)→(4,2)→(4,1)$

So, he takes 10 steps to unlock all the cars.
In the second case, He will select the spot $(1,2)$ and the path he takes will be $(1,2)→(1,3)→(2,3)→(2,2)→(2,1)→(3,1)→(3,2)$.
So, he takes 6 steps.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from sys import stdin\n\nfor _ in range(int(stdin.readline())):\n m, n = list(map(int, stdin.readline().split()))\n final = []\n arr = []\n val = 0\n extra = 0\n for j in range(m):\n  ans = list(map(str, stdin.readline().split()))\n  if ans.count('N') == n:\n   val += 1\n  else:\n   if val%2 == 0:\n    arr.append(ans)\n    extra += val\n   else:\n    arr.append(['N']*n)\n    arr.append(ans)\n    extra += (val-1)\n   val = 0\n\n for j in range(len(arr)):\n  ans = arr[j]\n  start = -1\n  for i in range(n):\n   if ans[i] == 'P':\n    start = i\n    break\n  if start != -1:\n   for i in range(n-1, -1, -1):\n    if ans[i] == 'P':\n     end = i\n     break\n  if start != -1:\n   if len(final) == 0:\n    final.append([start, end])\n   else:\n    if j%2 == 0:\n     if final[-1][0] > start:\n      final[-1][0] = start\n     else:\n      start = final[-1][0]\n    else:\n     if final[-1][1] < end:\n      final[-1][1] = end\n     else:\n      end = final[-1][1]\n    final.append([start, end])\n  else:\n   if len(final) != 0:\n    start, end = 0, n-1\n    if j%2 == 0:\n     if final[-1][0] > start:\n      final[-1][0] = start\n     else:\n      start = final[-1][0]\n    else:\n     if final[-1][1] < end:\n      final[-1][1] = end\n     else:\n      end = final[-1][1]\n    final.append([start, end])\n if len(final) == 0:\n  print(0)\n else:\n  count = 0\n  for ele in final:\n   count += (ele[1]-ele[0]+1)\n  print(count-1+extra)\n      \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14395