You are all alone in the jungle of N * M unit area.
Ofcourse the jungle is having wild animals.
All the animals are currently resting, but these animals are very sensitive to noise and if you reach nearby any animal, you will get killed up.
There is a single exit from jungle and you know it.You can run horizontally, vertically and diagonally .
Find the minimum steps to go out of jungle from your current position without getting killed.
If you step on exit point, you will get immediately teleported to safe place out of jungle.
Teleporting works only for humans and not for wild animals.
Also if multiple wild animals are near to each other, they all will attack and kill each other
i.e if there is a chain of wild animals , all of them will be destroyed.
Also if you come nearby multiple wild animals, they will share you equally. Beware and save yourself.
If they have choice between you other animals, they will prefer your meat then they will attack each other.

Contraints:
1 <= TEST <= 10000
2 <= N , M <= 1000
0 <= W <= N*M - 2
Occurances of Y and E are only once per test case

Input:
Take no of test cases input in TEST variable.
First line of every test will contain N and M i.e the height and width of jungle.
Next N lines contains a string of M characters.
These characters can be:
  Y : Your Position
  O : Blank unit in jungle
  W : Wild Animal
  E : Exit

Output:

Print the minimum steps to travel to go to exit point for every test case on new line.
If the way to exit is not possible or if you are getting killed print "-1" without quotes.

---

---

Sample Test Case 1 :
Input:
  1
  10 6
  OOWOOO
  WOOOOO
  OOOWOO
  OWWOOO
  OOOOOO
  OOOWOO
  OOOOOO
  OOOOOO
  OOEWOO
  OWOOOY
 
Output:
  13

Explanation:
Consider indexing from 1
Three animals in 3rd and 4th row are in a chain. Thus, they all will be destroyed.

See the Image below for Explanation

You step on Exit point in 13 steps.
Before wild animals kill you, you will be teleported to safe place.

---

Sample Test Case 2:
Input:
  1
  3 4
  YOOO
  WOOO
  WOOE
 
Output:
  -1

Explanation:

First, you will be killed by animal resting in 2nd row, as he will prefer your meat first.
OOOO
WOOO
WOOE

Then, they will kill each other.
OOOO
OOOO
OOOE