아기의 블록 놀이

마이키(Mikey)는 좋아하는 장난감 블록을 가지고 놀고 있습니다. 블록마다 알파벳 한 글자가 그려져 있습니다. 마이키는 자신의 블록을 모두 사용해 단어를 만들려고 하지만, 어떤 단어가 올바른지 알지 못하기 때문에 글자들로 만들 수 있는 모든 배열을 알파벳 순서(사전 순서)대로 하나씩 만들어 보며, 천재 형인 앨버트(Albert)에게 그 단어가 올바른 단어인지 물어봅니다. 마이키는 60초마다 단어 하나를 만들 수 있으며(질문하고 답을 듣는 시간 포함), 같은 단어를 두 번 만들지는 않습니다. 즉, 글자가 중복되어 같은 배열이 여러 번 나오더라도 그 단어는 한 번만 만듭니다.

앨버트는 마이키의 놀이를 좋아하지만, 특정 단어만은 마이키에게 가르치고 싶지 않습니다. 마이키가 그 금지된 단어를 만들기 시작하는 시점을 예측하여, 그 직전을 마이키의 취침 시각으로 알람을 맞출 수 있도록 앨버트를 도와주세요. 마이키가 가장 처음 가능한 단어를 이제 막 만들기 시작했다고 가정하며, 이 첫 단어를 만드는 시점을 0분으로 봅니다.

입력의 첫째 줄에는 테스트 케이스의 개수를 나타내는 양의 정수가 주어집니다. 그 다음 각 테스트 케이스마다:

• 찾으려는 금지된 단어가 한 줄에 주어집니다. 이 단어는 최대 20개의 대문자 알파벳으로 이루어져 있으며, 마이키의 블록 전체를 정확히 사용해 만들 수 있습니다.

각 테스트 케이스마다:

• 마이키가 가장 처음 가능한 단어를 이제 막 만들기 시작했다고 할 때, 금지된 단어에 도달하기까지 걸리는 시간을 분 단위로 한 줄에 출력합니다.