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.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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]
				elif final[-1][1] < end:
					final[-1][1] = end
				else:
					end = final[-1][1]
				final.append([start, end])
		elif 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]
			elif 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
		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)


try:
	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
		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


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)


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)


T = int(input())
for i in range(T):
	(m, n) = input().split()
	m = int(m)
	n = int(n)
	c = []
	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
	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
			elif '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
		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:
			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')
	elif '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