URI Online Judge | 3094

Guys' Truco 3.0

By Ygor Ribeiro, IFSULDEMINAS BR Brazil

Timelimit: 1

As you are tired of knowing, this game is very famous and therefore deserves several problems. This time, Ygor is the superstitious of the story. Ygor believes that his teammates are stealing and trying to get him out of the game right away, as he has been losing a lot of points and is about to leave the competition. As he doesn't want to leave so soon, he proposed a condition to redeem his points and his friends left, since they saw that he would never be able to meet such a challenge since it was not very easy.

Ygor also has his "lucky cards", which are {7, Q, J, K, A}. The proposed challenge was the following: Ygor will tell you how many cards must be removed from the pile so that only good sequences remain, if he succeeds, he gains +1 point and goes to Tibelo happy.

A sequence is said to be good if the student's lucky cards appear exactly in that order on the pile, not necessarily one after the other.

Example of cards left in the pile:

As we can see there are two good sequences, highlighted in blue and red. The cards that must be removed in order for the pile to remain with only these sequences are the cards {2, J, A, Q}, therefore 4 cards. ATTENTION: We cannot use the same card in two different sequences, once used in one, it cannot be used in another and the pile cannot have its order of cards exchanged

Input

The first line of input contains an integer N (1 <= N <= 20), which indicates the number of test cases. The next N lines contain a String S (1 <= |S| <= 1000), with no spaces, showing all the cards left in the pile after the cards were dealt to the players.

Output

For each line of test case, print the minimum number of cards that must be removed from the pile so that it is only with good strings.

Input Samples Output Samples

2
27JQ7JQAKJAKAQ
777QQQJJKKKAAA

4
4