사전

맥거핀 섬 사람들이 쓰는 언어의 알파벳은 로마자의 처음 아홉 글자 a, b, c, d, e, f, g, h, i로만 이루어진다. 단어는 모두 길이가 정확히 9이고, 이 아홉 글자를 각각 한 번씩 쓴다. 아홉 글자의 순열은 전부 단어이므로 이 언어의 단어는 $9! = 362880$개다.

가장 큰 사원의 도서관에는 이 언어의 사전이 있고, 단어 하나가 한 쪽을 차지한다. 사전의 배열 순서는 영어 사전과 같아서, 사전순으로 가장 앞선 abcdefghi가 1쪽이고 가장 뒤인 ihgfedcba가 362880쪽이다.

단어가 여러 개 주어질 때 각 단어가 사전의 몇 쪽에 있는지 구하라.

첫째 줄에 단어의 개수 $N$이 주어진다 ($1 \le N \le 6000$).

다음 $N$개 줄에 단어가 한 줄에 하나씩 주어진다. 각 단어는 a부터 i까지 아홉 글자를 각각 한 번씩 쓴 길이 9의 문자열이다.

입력에 주어진 순서대로 각 단어의 쪽 번호를 한 줄에 하나씩 출력한다.