This is an answer-submission problem.

Niuniu has recently become obsessed with a card game called Dou Dizhu. Dou Dizhu is a card game played with cards from A to K plus the two jokers. There are four cards for each rank from A to K (represented by A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K), and one each of the small joker (w) and big joker (W).

The rank order of the cards is as follows: 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A < 2 < w < W

In the NOIP, Niuniu learned the minimum number of turns required to play out all his cards. However, he was mocked by his friends because whether one can win a game seems to have nothing to do with how many turns it takes to play out the cards, and he didn't even know that "airplanes" could carry "wings." Now, Niuniu is playing cards with his friends again.

Niuniu or his friends can play cards according to the specified patterns each turn. The goal is to play out all their cards before the opponent does to win the game. The winner receives a reward of $x$, and the loser receives a penalty of $x$, where $x$ is the number of cards remaining in the loser's hand when the winner plays their last card.

The card patterns are defined as follows:

The rules for comparing card strengths are as follows:

1. Generally, cards can only be compared if they are of the same pattern and contain the same number of cards.
2. For singles, pairs, triplets, single sequences, double sequences, and triple sequences, compare the rank of the highest card.
3. For triplets with singles and triplets with pairs, compare the rank of the three cards of the same rank.
4. For quads with two singles and quads with two pairs, compare the rank of the four cards of the same rank.
5. For airplanes with wings and airplanes with double wings, compare the rank of the triple sequence.
6. Specifically, a rocket is greater than any other card combination.
7. Specifically, a bomb is greater than any card combination except for a rocket or a bomb with a higher rank.

Niuniu goes first and can play any valid card combination according to the rules above.

After one player plays a hand, the opponent has two choices: 1. Play a hand that is greater than the opponent's. 2. Pass.

When a player passes, the other player continues by playing any valid card pattern.

When a player plays their last card, all operations stop immediately, the game ends, and the reward/penalty is calculated.

Both Niuniu and his friends know all the cards in the opponent's hand through a special method, and they both know that the other knows their cards.

They both want to maximize their reward and minimize their penalty.

Since Niuniu's friend is very clever and will not make any mistakes, please help Niuniu calculate whether he can win. If he can, find the maximum reward he can obtain; if not, find the minimum penalty he must receive.

Input

Each test case contains several sets of data, ending with 0 0.

The first line of each set contains two positive integers, representing the number of cards in Niuniu's hand and the number of cards in his friend's hand, respectively.

The second line of each set contains a string, where each character represents the rank of a card in Niuniu's hand.

The third line of each set contains a string, where each character represents the rank of a card in his friend's hand.

Output

For each set of data, if Niuniu can win, output an integer $x$, where $x$ is the maximum reward he can obtain. If Niuniu cannot win, output an integer $-x$, where $x$ is the minimum penalty he must receive.

Examples

Input 1

1 1
3
4
0 0

Output 1

-1

Constraints

It is guaranteed that the cards given for both sides are valid. This problem is scored based on accuracy. For a test case, if your accuracy is $p$, the score is $\lfloor 20p^3 \rfloor$.

Note: During the competition, the evaluation for this problem will result in a direct score of 0.