Baby's Blocks

Mikey is playing with his favorite toy blocks, each showing one letter of the alphabet. He wants to make words using all of his blocks, but since he cannot tell valid words from invalid ones, he goes through every possible ordering of the letters in alphabetical (lexicographic) order, making them one at a time, and asks Albert, his genius brother, whether the word he made is a valid one. Mikey makes one word every sixty seconds (this includes asking the question and hearing the answer), and he never makes the same word twice — so even if repeated letters produce the same ordering more than once, he only makes that word once.

Albert enjoys Mikey's game, but there are certain words he would rather not teach him. Help Albert by predicting when Mikey will start making a particular forbidden word, so that he can set the bedtime alarm for just before that moment. Assume Mikey has just started making the very first possible word, and treat the moment he makes that first word as minute 0.

The first line of the input contains a positive integer, the number of test cases. Then for each test case:

• A line containing the forbidden word to look for, consisting of at most 20 upper case letters. This word can be formed by using all of Mikey's blocks exactly.

For each test case:

• One line containing the number of minutes it takes until the forbidden word is reached, assuming Mikey has just started making the first possible word.