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

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

입력

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

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

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

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

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

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

출력

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

예제 입력 1

3
7 1
...@#O.
5 2
#@#.O
4 0
O##@

예제 출력 1

HAHA!
HAHA!
HELP!