Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2728
Fighting against the Overlord

Time Limit: 5 Seconds      Memory Limit: 32768 KB

"Fighting against the Overlord" is a very popular poker game in China. This game uses a standard deck of 52 cards, plus 2 jokers, namely 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A, 2, Colorless Joker(denoted as L) and Colorful Joker(denoted as F), from LOW rank to HIGH rank.

The game is played between an "Overlord" and two "Peasants". At the beginning to the game, the overload has 20 poker cards and each peasant has 17 cards, then they play cards based on the rules which will be introduced shortly. If the overload first finishes with all his cards played, the overload wins, otherwise the two peasants win.

RULES:
A play of cards is legal IF AND ONLY IF it is in one of the following categories:

  • SINGLE: a single card. e.g, 3, 4, 5, ..., A, 2, L, F.
  • PAIR: two cards with the same rank. e.g. 33, 44, 55, ..., AA, 22.
  • TRIPLE: three cards with the same rank. e.g. 333, 444, 555, ... AAA, 222.
  • BOMB: four cards with the same rank, or the two jokers. e.g. 3333, 4444, 5555, ... AAAA, 2222, LF.
  • TRIPLE+SINGLE: e.g. 3334, 444K, ..., AAA3, 222F.
  • TRIPLE+PAIR: e.g. 33344, 444JJ, ..., AAA44, 22277.
  • SINGLE STRAIGHT: a straight of SINGLEs with at least FIVE cards(2, L and F can not appear in straight). e.g. 34567, ..., 678910JQKA.
  • PAIR STRAIGHT: a straight of PAIRs with at least THREE PAIRs(2, L and F can not appear in straight). e.g. 334455, ..., 991010JJQQKK.
  • TRIPLE STRAIGHT: a straight of TRIPLEs with at least TWO TRIPLEs(2, L and F can not appear in straight). e.g. 333444, ..., 999101010JJJQQQKKK.
  • TRIPLE STRAIGHT with wings: a TRIPLE STRAIGHT, plus SINGLEs or PAIRs with the same number of TRIPLEs the TRIPLE STRAIGHT has. e.g. 3334448Q, ..., 5556667771010QQKK.
  • 4+2: four cards with the same rank, plus TWO SINGLEs or TWO PAIRs. e.g. 333345, ... 222266KK.

In this problem, given n(0 <= n <= 20) cards, you are asked to write a program, which outputs the minimum number of plays the player needs to play all his cards. Please note that you don't need to consider the other players' strategies.

Input

The input file contains several test cases. Each test case has two lines. The first line is an integer m, indicating the number of cards and the second line contains m cards.

Output

For each test case, output the minimum number of plays on a single line.

Sample Input

8
3 3 3 4 4 4 3 4
20
3 4 5 6 7 8 9 10 J Q 5 6 7 8 9 10 J Q K A
20
F L 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 J Q K

Sample Output

1
2
1


Author: JIANG, Jiefeng
Source: Zhejiang University Local Contest 2006
Submit    Status