황금의 콘깬

콘깬(Khon Kaen)은 태국 북동부에 있는 주다. 이 주의 표어는 다음과 같다.

พระธาตุขามแก่น เสียงแคนดอกคูน ศูนย์รวมผ้าไหม ร่วมใจผูกเสี่ยว
เที่ยวขอนแก่นนครใหญ่ ไดโนเสาร์สิรินธรเน่ สุดเท่เหรียญทองมวยโอลิมปิก

표어에는 "황금"이 두 번 등장한다. 첫 번째는 주의 공식 꽃인 ดอกคูน, 곧 "골든 샤워"다. 두 번째는 금메달인데, 콘깬 출신 솜락 캄싱이 딴 태국 최초의 올림픽 금메달을 가리킨다.

황금의 주를 기념하려고, 주어진 글자로 GOLDEN이라는 단어를 몇 개 만들 수 있는지 센다. 글자는 모두 A부터 Z까지의 대문자다. GOLDEN 한 개를 만들려면 G, O, L, D, E, N이 각각 정확히 하나씩 필요하다.

예를 들어 글자열이 GOOOOOOOOLDENN이면 GOLDEN을 한 개 만들 수 있고, O와 N이 남는다.

글자열이 여러 개 주어질 때, 각 글자열로 GOLDEN을 최대 몇 개 만들 수 있는지 구하라. 글자가 남을 수도 있고, B처럼 필요 없는 글자가 섞여 있을 수도 있다.

첫 줄에 테스트 케이스의 개수 $N$ ($1 \le N \le 100$)이 주어진다. 다음 $N$개 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 A부터 Z까지의 대문자로 이루어진 글자열이고, 글자 순서는 뒤섞여 있을 수 있으며 같은 글자가 여러 번 나올 수도 있다. 한 줄의 길이는 최대 400이다.

각 테스트 케이스마다 주어진 글자로 만들 수 있는 GOLDEN의 최대 개수를 한 줄에 하나씩 출력한다. 글자가 남아도 된다.