“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island ("Остров Обезьян"). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с 6 строками и 7 столбцами. Комнаты "R" показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного "g", а Ли Чак – с участка "l". У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом "e" на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный "e"). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не "R" или "e") или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от "g" до "e") такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени. Например, последовательность "Влево, Вверх, Вверх, Вверх, Вправо" (за 5 единиц времени) представляет безопасный путь на приведенной карте, потому что независимо от того, что Ли Чак делает в эти 5 единиц времени, он не может поймать Гайбраша.

Входные данные

Первая строка входа содержит единственное целое число - количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа R и C (4 <= R, C <= 30), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют R строк, каждая содержит C символов, представляющих карту. Есть единственные отметки "g", "l" и "e" на карте.

Изначально пустые участки без скал обозначаются символом пробела. Все участки, расположенные у какой-либо границы карты, заполнены скалами.

Выходные данные

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово "YES", и слово "NO", если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более 1000 единиц времени для прохождения по нему Гайбраша.