Problem C
Cheating at War

War is a classic and very simple two-player card game played with a standard $52$-card deck. The deck is shuffled and split into two equal-sized piles, one for each player, with cards face down. To play, both players turn over the top card of their draw pile. The player whose card rank is higher (suit doesn’t matter) wins both cards. In our variant of War for this problem, when a tie in rank occurs, both players take their one card back.¹ The ranks of the cards, from highest to lowest, are [A]ce, [K]ing, [Q]ueen, [J]ack, [T]en, $9$, $8$, $7$, $6$, $5$, $4$, $3$, and $2$. After the card battle is settled, both players would turn over the next card in their draw piles for the following battle, and so forth. Also in our variant, after the initial $26$-card piles have been exhausted, both players count the cards they have won, and the player with the most cards wins the game.

Yraglac found himself playing War with a friend, and the first ten card battles of a game went like this:

At this point in the game, Yraglac would have won a total of $10$ cards.

After a few games, Yraglac was bored out of his mind because the game, clearly, has absolutely no element of strategy whatsoever! At the beginning of the next game, when his friend wasn’t looking, he decided to take a peek through both piles of cards and wondered, “How many cards could I win if I could rearrange my own pile of cards?” Now there’s a challenge worthy of his mighty brain!

It turned out for Yraglac that cheating at War was a little harder than he initially thought. Can you help by writing a program that, given lists of the cards in Yraglac’s opponent’s pile and in his own pile, determines the most cards Yraglac can win if he could rearrange the cards in his draw pile in any order he likes?

Input

The first line of the input contains a single integer, $1\le N\le 50$, indicating the number of games of war to be played. Following, there are two lines of input for each game. The first of the two lines contains a $26$-character string indicating the cards in the opponent’s pile, in the order that they will be played. Non-numeric cards are encoded with a single capital letter as described in the problem statement. The second of the two lines indicates the $26$ cards in Yraglac’s pile. Both piles together will always form the set of cards in a standard $52$-card deck.

Output

For each game of War described in the input, output on a single line the highest number of cards Yraglac can win if he were able to rearrange his pile of cards to be played in any order.

3
3J665T72457Q2J3AA9K3TK7T5A
296K979725JQA3K686679KT338
AKQJT98765432AKQJT98765432
AKQJT98765432AKQJT98765432
AAAAKKKKQQQQJJJJTTTT999988
22223333444455556666777788

42
48
2