마이티는 길이가 N인 1차원 세상의 어딘가에 위치해 있고, 1차원 세상의 어딘가에 위치한 탈출구로 이동해 탈출하려고 합니다. 마이티는 1차원 세상에서 현재 위치한 칸에서 왼쪽 칸이나 오른쪽 칸으로 움직일 수 있습니다. 마이티가 가는 길에 벽이 있을 수도 있지만 마이티는 최대 M개의 벽을 부수고 지나갈 수 있습니다.

그런데 어느 날, 1차원 세상에 인피니티 건틀렛이 떨어졌습니다. 마이티가 인피니티 건틀렛이 있는 칸으로 이동해서 손에 끼고 손가락을 튕기기만 하면 1차원 세상의 모든 벽을 부술 수 있습니다.

마이티가 위치한 1차원 세상을 표현한 지도가 주어질 때 1차원 세상을 탈출할 수 있을지 구해주세요.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스의 첫째 줄에 1차원 세상의 길이 ~N\ (3 \le N \le 8)~과 마이티가 벽을 부술 수 있는 최대 횟수 ~M\ (0 \le M \le N - 3)~이 주어집니다.

둘째 줄에 1차원 세상을 표현한 길이 N짜리 문자열 S가 주어집니다.

문자열 S에서 @ 는 단 한 번 등장하며, 마이티를 의미합니다.

문자열 S에서 알파벳 대문자 O 는 단 한 번 등장하며, 마이티가 이동하려는 탈출구를 의미합니다.

문자열 S에서 알파벳 대문자 G 는 단 한 번 등장하며, 인피니티 건틀렛을 의미합니다.

문자열 S에서 등장하는 나머지 문자는 . 이거나 # 입니다. . 은 빈 칸을 의미합니다. 마이티는 빈 칸으로 자유롭게 이동할 수 있습니다. # 은 벽을 의미합니다. 마이티는 벽이 있는 칸으로 이동할 수 없지만, 최대 M개의 벽은 부술 수 있습니다.

출력

각 테스트 케이스마다 마이티가 1차원 세상을 탈출할 수 있다면 HAHA! 를 출력합니다. 그렇지 못하다면 HELP! 를 출력합니다. 모두 대문자로 출력해야 하는 것에 유의하세요.

예제 입력 1

4
7 1
@####OG
8 2
G###@##O
8 2
O###@##G
5 0
OG##@

예제 출력 1

HELP!
HAHA!
HAHA!
HELP!