D. Poker
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Poker is played with a standard 52-card deck (13 ranks and 4 suits). The ranks of the cards, in increasing order, are: 2, 3, ..., 10, Jack, Queen, King and Ace. Given a poker table, with two players, your task is to determine the winner.

Each player has two cards in his hand and there are five common cards to both players. Whichever player has the most valuable 5-card hand, choosing from his own cards and the one on the table, wins. A card on the table may be used by both players at the same time and a player may ignore zero, one or both of his own cards.

To determine the value of a 5-card hand, it is identified as one of the hand types listed below. If the same hand fits more than one type, the most valuable one is chosen. If both players' hands fit the same type, the tie is broken by some rule specific to that type.

The type list, from least to most valuable, and their respective tie-breaking rule are:

  • Highest card: If the hand does not fit any of the other types. To break the tie, the five cards are compared, one by one, from highest to lowest rank, until one hand has a higher card then the other;
  • One pair: Two cards of the same rank. The tie-breaker is similar the rule in Highest card, first comparing the pair, and then the other three cards;
  • Two pairs: Two pairs of different rank. The tie-breaker is first by the most valuable pair, then by the second, then by the last card;
  • Three of a kind: Three cards of the same rank. The tie-breaker is analogous to the one in One pair, first compare the triple, then the other two cards;
  • Straight: Five cards in a sequence. In this case, the Ace may be either the highest rank (after the King) or the lowest (before the 2). The tie-breaker is done by the card of highest rank, considering that Ace has the lowest rank if it comes before a 2;
  • Flush: Five cards of the same suit. The tie-breaker is done like in Highest card;
  • Full House: A three of a kind with a pair. The tie-breaker is done by the rank of the three of a kind, and then by the pair;
  • Four of a kind: Four cards of the same rank. The tie-breaker is done by the rank of the four of a kind, and then by the last card;
  • Straight Flush: Straight and Flush at the same time. The tie-breaker is the same as in Straight.

    Notice that it is possible for the tie to persist even after the tie-breaker rules are applied. The suits of a card are only used to define a Flush, and are not used in any tie-breaker rule.

Input

On the first line, an integer T, the number of test cases.

Each test case is given in three lines. The first two lines have the description of two cards each, the cards of the first player, and of the second. The last line has the description of five cards, the cards on the table.

The description of each card is given by two characters, the rank and the suit, as given in the table.

Limits

  • 1 ≤ T ≤ 105
  • For each test case, all cards are valid and distinct.
Output

For each test, print 1 if the first player wins, 2 if the second player wins, and 0 if there is a tie, even after applying the tie-breaker rules.

Example
Input
3
Ts Js
Tc Jc
Qs Qc Ks Kc As
As 7d
Ah 8s
Ac Ad 9s Jh Kc
As 7d
Ah 8s
Ac Ad 6s 3h Kc
Output
1
0
2