This page is still under construction.

Parts of this page are still being built. What you see may change.

Romantic Date

Interview

Time limit1sMemory limit128 MB

Summary
Given Wibowo's 26 cards, find the maximum number of rounds he can win by pairing his cards against his opponent's 26 cards in the best order.
Level

Medium5 of 10

Topics
Greedy, Sorting, Two pointers
Solved
No attempts yet

Problem

Wibowo and his girlfriend play with a deck of 52 distinct cards. Each card has a number and a suit.

  • Numbers, from lowest to highest: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.
  • Suits, from weakest to strongest: Diamond, Club, Heart, Spade.

When two cards are compared, the card with the higher number wins. If both cards have the same number, the card with the stronger suit wins. Because the deck contains no duplicates, one card always beats the other.

The deck is split so that Wibowo and his girlfriend each hold 26 cards. The game lasts 26 rounds. In each round both players simultaneously reveal one card from their hand and compare them; the owner of the winning card scores one point.

Wibowo knows exactly which 26 cards he holds (his girlfriend holds the other 26). Assuming he can pair his cards against hers in the most favourable order, determine the maximum number of points Wibowo can score.

Input

The first line contains an integer TT (T≤100T \le 100), the number of test cases.

Each of the next TT lines describes one test case and contains Wibowo's 26 cards separated by single spaces. Each card is written with two characters: the first is its number and the second is its suit.

  • Number characters: 2, 3, 4, 5, 6, 7, 8, 9, T (10), J (Jack), Q (Queen), K (King), A (Ace).
  • Suit characters: D (Diamond), C (Club), H (Heart), S (Spade).

All 26 cards in a hand are distinct.

Output

For each test case, print on its own line a single integer: the maximum number of points Wibowo can score with the given hand.

Examples3

  1. Example 1

    Input
    3
2D 2C 2H 2S 3D 3C 3H 3S 4D 4C 4H 4S 5D 5C 5H 5S 6D 6C 6H 6S 7D 7C 7H 7S 8D 8C
8H 8S 9D 9C 9H 9S TD TC TH TS JD JC JH JS QD QC QH QS KD KC KH KS AD AC AH AS
2D TC 2C 9S 6H TH TD 8H 6S 3C 5H 3S TS 4C 5S JD 3D 2H 6C 7S 9C 6D 8D 4H 9H 5C
    Expected output
    0
26
11

  2. Example 2

    Input
    1
2D 2C 2H 2S 3D 3C 3H 3S 4D 4C 4H 4S 5D 5C 5H 5S 6D 6C 6H 6S 7D 7C 7H 7S 8D 8C
    Expected output
    0

  3. Example 3

    Input
    1
8H 8S 9D 9C 9H 9S TD TC TH TS JD JC JH JS QD QC QH QS KD KC KH KS AD AC AH AS
    Expected output
    26