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.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin

for _ in range(int(stdin.readline())):
 m, n = list(map(int, stdin.readline().split()))
 final = []
 arr = []
 val = 0
 extra = 0
 for j in range(m):
  ans = list(map(str, stdin.readline().split()))
  if ans.count('N') == n:
   val += 1
  else:
   if val%2 == 0:
    arr.append(ans)
    extra += val
   else:
    arr.append(['N']*n)
    arr.append(ans)
    extra += (val-1)
   val = 0

 for j in range(len(arr)):
  ans = arr[j]
  start = -1
  for i in range(n):
   if ans[i] == 'P':
    start = i
    break
  if start != -1:
   for i in range(n-1, -1, -1):
    if ans[i] == 'P':
     end = i
     break
  if start != -1:
   if len(final) == 0:
    final.append([start, end])
   else:
    if j%2 == 0:
     if final[-1][0] > start:
      final[-1][0] = start
     else:
      start = final[-1][0]
    else:
     if final[-1][1] < end:
      final[-1][1] = end
     else:
      end = final[-1][1]
    final.append([start, end])
  else:
   if len(final) != 0:
    start, end = 0, n-1
    if j%2 == 0:
     if final[-1][0] > start:
      final[-1][0] = start
     else:
      start = final[-1][0]
    else:
     if final[-1][1] < end:
      final[-1][1] = end
     else:
      end = final[-1][1]
    final.append([start, end])
 if len(final) == 0:
  print(0)
 else:
  count = 0
  for ele in final:
   count += (ele[1]-ele[0]+1)
  print(count-1+extra)
      


for _ in range(int(input())):
 
 r,c=map(int,input().split())
 
 ans=0
 
 last=-1
 flag=0
 
 cnt=0
 check=1
 
 for i in range(r):
  
  j=0
  
  values=[]
  
  for car in input().split():
   
   if(car=="P"):
    values.append(j)
    
   j+=1
   
  #print(values)
  
  
  
  if(len(values)==0):
   if(flag==0):
    continue
    
   if(flag==check):
    
    cnt+=1
    if(i==r-1):
     ans-=1
    continue
    
   if(flag>check):
    check=flag
    ans+=cnt
    cnt=0
    continue
    
 
  
  flag+=1

  if(i%2==1):

   ans+=abs(min(values)-max(values))+1
  
   if(i==r-1):
    ans-=1
    
    ans+=cnt
    
   if(last==-1):
    last=min(values)
   else:
    
    ans+=abs(last-max(values))
   
   last=min(values)

  else:
   
   ans+=abs(max(values)-min(values))+1
   
   if(i==r-1):
    ans-=1
    ans+=cnt

   if(last==-1):
    last=max(values)
   else:
    ans+=abs(last-min(values))

   last=max(values)
  #print(ans)




 print(ans)

try:
# if(True):
 for _ in range(int(input())):
  m,n=map(int,input().split())
  c=[]
  last=0
  flag=True
  rowstart=0
  rowend=0
  for i in range(m):
   k=list(input().split())
   co=0
   k.append(-1)
   k.append(-1)
   for j in range(len(k)):
    if(k[j]=="P"):
     co+=1
     if(co==1):
      k[-2]=j
     k[-1]=j
     rowend=i
    
   if(k[-1]!=-1 and flag):
    flag=False
    rowstart=i
    if(i%2==0):
     last=k[-2]
    else:
     last=k[-1]
   c.append(k)
  count=0
#         print(c)
  
  for i in range(rowstart,rowend+1):
   
   if(i%2==0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-2])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-1]
   elif(i%2!=0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-1])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-2]
   count+=1
  print(count-1)
 
 
 
except:
 pass

for _ in range(int(input())):
 
 r,c=map(int,input().split())
 
 ans=0
 
 last=-1
 flag=0
 
 cnt=0
 check=1
 
 for i in range(r):
  
  j=0
  
  values=[]
  
  for car in input().split():
   
   if(car=="P"):
    values.append(j)
    
   j+=1
   
  #print(values)
  
  
  
  if(len(values)==0):
   if(flag==0):
    continue
    
   if(flag==check):
    
    cnt+=1
    if(i==r-1):
     ans-=1
    continue
    
   if(flag>check):
    check=flag
    ans+=cnt
    cnt=0
    continue
    
 
  
  flag+=1

  if(i%2==1):

   ans+=abs(min(values)-max(values))+1
  
   if(i==r-1):
    ans-=1

   if(last==-1):
    last=min(values)
   else:
    
    ans+=abs(last-max(values))
   
   last=min(values)

  else:
   
   ans+=abs(max(values)-min(values))+1
   
   if(i==r-1):
    ans-=1

   if(last==-1):
    last=max(values)
   else:
    ans+=abs(last-min(values))

   last=max(values)
  #print(ans)




 print(ans)

try:
# if(True):
 for _ in range(int(input())):
  m,n=map(int,input().split())
  c=[]
  last=0
  flag=True
  rowstart=0
  rowend=0
  for i in range(m):
   k=list(input().split())
   co=0
   k.append(-1)
   k.append(-1)
   for j in range(len(k)):
    if(k[j]=="P"):
     co+=1
     if(co==1):
      k[-2]=j
     k[-1]=j
     rowend=i
    
   if(k[-1]!=-1 and flag):
    flag=False
    rowstart=i
    if(i%2==0):
     last=k[-2]
    else:
     last=k[-1]
   c.append(k)
  count=0
#         print(c)
  
  for i in range(rowstart,rowend+1):
   
   if(i%2==0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-2])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-1]
   elif(i%2!=0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-1])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-2]
   count+=1
  print(count-1)
 
 
 
except:
 pass

from sys import stdin

for _ in range(int(stdin.readline())):
 m, n = list(map(int, stdin.readline().split()))
 final = []
 for j in range(m):
  ans = list(map(str, stdin.readline().split()))
  start = -1
  for i in range(n):
   if ans[i] == 'P':
    start = i
    break
  if start != -1:
   for i in range(n-1, -1, -1):
    if ans[i] == 'P':
     end = i
     break
  if start != -1:
   if len(final) == 0:
    final.append([start, end])
   else:
    if j%2 == 0:
     if final[-1][0] > start:
      final[-1][0] = start
     else:
      start = final[-1][0]
    else:
     if final[-1][1] < end:
      final[-1][1] = end
     else:
      end = final[-1][1]
    final.append([start, end])
  else:
   if len(final) != 0:
    start, end = 0, n-1
    if j%2 == 0:
     if final[-1][0] > start:
      final[-1][0] = start
     else:
      start = final[-1][0]
    else:
     if final[-1][1] < end:
      final[-1][1] = end
     else:
      end = final[-1][1]
    final.append([start, end])
 if len(final) == 0:
  print(0)
 else:
  count = 0
  for ele in final:
   count += (ele[1]-ele[0]+1)
  print(count-1)
      
   
  


# cook your dish here
try:
# if(True):
 for _ in range(int(input())):
  m,n=map(int,input().split())
  c=[]
  last=0
  flag=True
  rowstart=0
  rowend=0
  for i in range(m):
   k=list(input().split())
   co=0
   k.append(-1)
   k.append(-1)
   for j in range(len(k)):
    if(k[j]=="P"):
     co+=1
     if(co==1):
      k[-2]=j
     k[-1]=j
     rowend=i
    
   if(k[-1]!=-1 and flag):
    flag=False
    rowstart=i
    if(i%2==0):
     last=k[-2]
    else:
     last=k[-1]
   c.append(k)
  count=0
#         print(c)
  
  for i in range(rowstart,rowend+1):
   
   if(i%2==0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-2])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-1]
   elif(i%2!=0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-1])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-2]
   count+=1
  print(count-1)
 
 
 
except:
 pass

from sys import stdin

for _ in range(int(stdin.readline())):
 m, n = list(map(int, stdin.readline().split()))
 final = []
 for j in range(m):
  ans = list(map(str, stdin.readline().split()))
  start = -1
  for i in range(n):
   if ans[i] == 'P':
    start = i
    break
  if start != -1:
   for i in range(n-1, -1, -1):
    if ans[i] == 'P':
     end = i
     break
  if start != -1:
   if len(final) == 0:
    final.append([start, end])
   else:
    if j%2 == 0:
     if final[-1][0] > start:
      final[-1][0] = start
     else:
      start = final[-1][0]
    else:
     if final[-1][1] < end:
      final[-1][1] = end
     else:
      end = final[-1][1]
    final.append([start, end])
 if len(final) == 0:
  print(0)
 else:
  count = 0
  for ele in final:
   count += (ele[1]-ele[0]+1)
  print(count-1)
      
   
  


for _ in range(int(input())):
 
 r,c=map(int,input().split())
 
 ans=0
 
 last=-1
 flag=0
 
 cnt=0
 check=1
 
 for i in range(r):
  
  j=0
  
  values=[]
  
  for car in input().split():
   
   if(car=="P"):
    values.append(j)
    
   j+=1
   
  #print(values)
  
  
  
  if(len(values)==0):
   if(flag==0):
    zerocnt=1
    continue
    
   if(flag==check):
    
    cnt+=1
    if(i==r-1):
     ans-=1
    continue
    
   if(flag>check):
    check=flag
    ans+=cnt-1
    cnt=0
    continue
    
 
  
  flag+=1

  if(i%2==1):

   ans+=abs(min(values)-max(values))+1
  
   if(i==r-1):
    ans-=1

   if(last==-1):
    last=min(values)
   else:
    
    ans+=abs(last-max(values))
   
   last=min(values)

  else:
   
   ans+=abs(max(values)-min(values))+1
   
   if(i==r-1):
    ans-=1

   if(last==-1):
    last=max(values)
   else:
    ans+=abs(last-min(values))

   last=max(values)
  #print(ans)




 print(ans)

y=int(input())
while(y):
 y-=1
 n,m=map(int,input().split())
 l1=[]
 for i in range(n):
  l1.append(0)
 k=-1
 l3=[]
 l4=[]
 for i in range(n):
  k1=-1
  k2=-1
  l2=input().split()
  for j in range(len(l2)):
   if(l2[j]=='P'):
    if(k==-1):
     k=i
    if(k1==-1):
     k1=j
    k2=j
  if(k1==-1):
   l1[i]=1
  l3.append(k1)
  l4.append(k2)
 if(n==1 or k==n-1 or k==-1):
  if(n==1):
   print(l4[0]-l3[0])
  else:
   print(l4[n-1]-l3[n-1])
  continue
 c=0
 if(k%2!=0):
  a1=l4[k]
 else:
  a1=l3[k]
 for i in range(k,n-1):
  if(l3[i+1]==-1):
   if(i%2!=0):
    l3[i+1]=l4[i+1]=l3[i]
   else:
    l3[i+1]=l4[i+1]=l4[i]
  if(i%2!=0):
   a2=min(l3[i+1],l3[i])
   c+=(a1-a2)
   a1=a2
  else:
   a2=max(l4[i],l4[i+1])
   c+=(a2-a1)
   a1=a2
 if((n-1)%2!=0):
  c+=a1-l3[n-1]
 else:
  c+=l4[n-1]-a1
 c+=n-1
 for i in range(n-1,-1,-1):
  if(l1[i]==1):
   c-=1
  else:
   break
 c-=k
 print(c)

try:
# if(True):
 for _ in range(int(input())):
  m,n=map(int,input().split())
  c=[]
  last=0
  flag=True
  rowstart=0
  rowend=0
  for i in range(m):
   k=list(input().split())
   co=0
   k.append(-1)
   k.append(-1)
   for j in range(len(k)):
    if(k[j]=="P"):
     co+=1
     if(co==1):
      k[-2]=j
     k[-1]=j
     rowend=i
    
   if(k[-1]!=-1 and flag):
    flag=False
    rowstart=i
    if(i%2==0):
     last=k[-2]
    else:
     last=k[-1]
   c.append(k)
  count=0
#         print(c)
  
  for i in range(rowstart,rowend+1):
   
   if(i%2==0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-2])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-1]
   elif(i%2!=0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-1])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-2]
   count+=1
  print(count-1)
 
 
 
except:
 pass

def countt(n):
 for i in range(5):
  pass
 return n
t = int(input())
for _ in range(t):
 m, n = map(int, input().split())
 arr = []
 p = []
 for x in range(m):
  temp = [i for i in input().split()]
  if(x % 2 == 0):
   for j in range(n):
    if(temp[j] == 'P'):
     p.append([x+1,j+1])
  else:
   for j in range(n-1, -1, -1):
    if(temp[j] == 'P'):
     p.append([x+1, j+1])
  arr.append(temp)
 c = countt(20)
 res = c
 l = len(p)
 for i in range(l):
  if(i+1 < l):
   res += abs(p[i][0] - p[i+1][0]) + abs(p[i][1] - p[i+1][1])
 print(res-c)

# cook your dish here
try:
# if(True):
 for _ in range(int(input())):
  m,n=map(int,input().split())
  c=[]
  last=0
  flag=True
  rowstart=0
  rowend=0
  for i in range(m):
   k=list(input().split())
   co=0
   k.append(-1)
   k.append(-1)
   for j in range(len(k)):
    if(k[j]=="P"):
     co+=1
     if(co==1):
      k[-2]=j
     k[-1]=j
     rowend=i
    
   if(k[-1]!=-1 and flag):
    flag=False
    rowstart=i
    if(i%2==0):
     last=k[-2]
    else:
     last=k[-1]
   c.append(k)
  count=0
#         print(c)
  
  for i in range(rowstart,rowend+1):
   
   if(i%2==0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-2])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-1]
   elif(i%2!=0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-1])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-2]
   count+=1
  print(count-1)
 
 
 
except:
 pass

try:
# if(True):
 for _ in range(int(input())):
  m,n=map(int,input().split())
  c=[]
  last=0
  flag=True
  rowstart=0
  rowend=0
  for i in range(m):
   k=list(input().split())
   co=0
   k.append(-1)
   k.append(-1)
   for j in range(len(k)):
    if(k[j]=="P"):
     co+=1
     if(co==1):
      k[-2]=j
     k[-1]=j
     rowend=i
    
   if(k[-1]!=-1 and flag):
    flag=False
    rowstart=i
    if(i%2==0):
     last=k[-2]
    else:
     last=k[-1]
   c.append(k)
  count=0
#         print(c)
  
  for i in range(rowstart,rowend+1):
   
   if(i%2==0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-2])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-1]
   elif(i%2!=0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-1])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-2]
   count+=1
  print(count-1)
 
 
 
except:
 pass

# cook your dish here
T = int(input())

for i in range(T):
 m, n = input().split()
 m = int(m)
 n = int(n)
 c = []
 # m = 4
 # n  = 5
 # c = [['N', 'P', 'N', 'N', 'P'], ['N', 'N', 'P', 'N', 'N'], ['N', 'P', 'N',         'N', 'N'], ['P', 'N', 'N', 'N', 'N']]
 start_pos_m = -1
 start_pos_n = -1
 for j in range(m):
  c.append(input().split())
  if('P' in c[-1] and start_pos_m == -1):
   start_pos_n = c[-1].index('P')
   start_pos_m = j
 # print(c)
 cur_pos_m = start_pos_m
 cur_pos_n = start_pos_n
 next_pos_m = cur_pos_m
 number_of_steps = 0
 next_pos_n = start_pos_n
 for j in range(start_pos_m, m - 1):
  if('P' not in c[j]):
   if(j % 2 == 0):
    if('P' in c[j + 1][next_pos_n + 1: n]):
     print(1)
     rev = c[j + 1][: : -1]
     next_pos_n = n - 1 - rev.index('P')
     number_of_steps += next_pos_n - cur_pos_n
     cur_pos_n = next_pos_n
   else:
    if('P' in c[j + 1][0 : next_pos_n]):
     next_pos_n = c[j + 1].index('P')
     number_of_steps += cur_pos_n - next_pos_n
     cur_pos_n = next_pos_n
   if('P' in c[j + 1]):
    number_of_steps += j - cur_pos_m 
   # print(c[j])

  elif(j % 2 == 0):    
   rev = c[j][: : -1]
   next_pos_n = n - 1 - rev.index('P')
   if('P' in c[j + 1][next_pos_n : n]):
    rev = c[j + 1][: : -1]
    next_pos_n = n - 1 - rev.index('P')
   number_of_steps += next_pos_n - cur_pos_n
   cur_pos_n = next_pos_n
   number_of_steps += 1
  else:
   # rev = c[j][:: -1]
   # print("rev : ", rev)
   next_pos_n = c[j].index('P')
   if('P' in c[j + 1][0 : next_pos_n + 1]):
    next_pos_n = c[j + 1].index('P')
   number_of_steps += cur_pos_n - next_pos_n
   cur_pos_n = next_pos_n
   number_of_steps += 1
  cur_pos_m = j

 if(m % 2 == 0):
  if('P' in c[-1][0 : cur_pos_n]):
   number_of_steps += cur_pos_n - c[-1][0 : cur_pos_n].index('P') 
 else:
  if('P' in c[-1][cur_pos_n + 1 : :]):
   number_of_steps += n - 1 - c[-1][:: -1].index('P') - cur_pos_n
 
 print(number_of_steps)

try:
 for _ in range(int(input())):
  M,N=map(int,input().split())
  dp=[]
  for i in range(M):
   l=input()
   l=l.replace(' ','')
   l=l.upper()
   dp.append(list(l))
  pos=[]
  for i in range(M):
   if (i+1)%2!=0:
    for j in range(0,N,1):
     if dp[i][j]=="P":
      pos.append([i,j])
   else:
    for j in range(N-1,-1,-1):
     if dp[i][j]=="P":
      pos.append([i,j])
  s=0
  for i in range(len(pos)-1):
   for j in range(len(pos[i])):
    s+=abs(pos[i][j]-pos[i+1][j])
  print(s)
except:
 pass

for _ in range(int(input())):
 
 r,c=map(int,input().split())
 
 ans=0
 
 last=-1
 flag=0
 
 for i in range(r):
  
  j=0
  
  values=[]
  
  for car in input().split():
   
   if(car=="P"):
    values.append(j)
    
   j+=1
   
  #print(values)
  
  if(len(values)==0):
   if(flag==0):
    continue
   else:
    ans+=1
    continue
    
  flag=1

  if(i%2==1):

   ans+=abs(min(values)-max(values))+1
  
   if(i==r-1):
    ans-=1

   if(last==-1):
    last=min(values)
   else:
    
    ans+=abs(last-max(values))
   
   last=min(values)

  else:
   
   ans+=abs(max(values)-min(values))+1
   
   if(i==r-1):
    ans-=1

   if(last==-1):
    last=max(values)
   else:
    ans+=abs(last-min(values))

   last=max(values)
  #print(ans)




 print(ans)

# cook your dish here
try:
# if(True):
 for _ in range(int(input())):
  m,n=map(int,input().split())
  c=[]
  last=0
  flag=True
  rowstart=0
  rowend=0
  for i in range(m):
   k=list(input().split())
   co=0
   k.append(-1)
   k.append(-1)
   for j in range(len(k)):
    if(k[j]=="P"):
     co+=1
     if(co==1):
      k[-2]=j
     k[-1]=j
     rowend=i
    
   if(k[-1]!=-1 and flag):
    flag=False
    rowstart=i
    if(i%2==0):
     last=k[-2]
    else:
     last=k[-1]
   c.append(k)
  count=0
#         print(c)
  
  for i in range(rowstart,rowend+1):
   
   if(i%2==0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-2])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-1]
   elif(i%2!=0 and c[i][-1]!=-1):
    count+=abs(last-c[i][-1])
    count+=c[i][-1]-c[i][-2]
    last=c[i][-2]
   count+=1
  print(count-1)
 
 
 
except:
 pass