Tokitsukaze играет в игру, произошедшую от японской игры маджонг. В этой игре у нее в руке есть три тайла. Каждый тайл имеет масть (manzu, pinzu или souzu) и число (цифра от \(1\) до \(9\)). В этой задаче мы используем одну цифру и одну букву нижнего регистра, являющуюся первой буквой масти, для представления тайла. Все возможные тайлы представляются комбинациями 1m, 2m, \(\ldots\), 9m, 1p, 2p, \(\ldots\), 9p, 1s, 2s, \(\ldots\), 9s.
Для того, чтобы выиграть, Tokitsukaze должна иметь хотя бы одно mentsu (определение ниже) в руке, поэтому иногда ей нужно брать дополнительные тайлы. Она может взять сколько угодно каких угодно тайлов, даже тех, которые уже есть в ее руке.
Вычислите минимальное количество дополнительных тайлов, которое ей нужно взять чтобы выиграть.
Вот некоторые полезные определения, связанные с этой игрой:
- Mentsu, также известное как слияние, это либо koutsu, либо shuntsu;
- Koutsu, также известное как тройка, это три идентичных тайла, например [1m, 1m, 1m], однако [1m, 1p, 1s] и [1m, 4m, 7m] НЕ являются koutsu;
- Shuntsu, также известное как последовательность, это три последовательно пронумерованных тайла одной масти, например [1m, 2m, 3m] или [5s, 7s, 6s], однако [9m, 1m, 2m] и [1m, 2p, 3s] НЕ являются shuntsu.
Немного примеров:
- [2m, 3p, 2s, 4m, 1s, 2s, 4s] не содержит ни koutsu, ни shuntsu, поэтому не содержит mentsu;
- [4s, 3m, 3p, 4s, 5p, 4s, 5p] содержит koutsu [4s, 4s, 4s], не содержит shuntsu, поэтому содержит mentsu;
- [5p, 5s, 9m, 4p, 1s, 7p, 7m, 6p] не содержит koutsu, но содержит shuntsu: [5p, 4p, 6p] или [5p, 7p, 6p], поэтому это mentsu.
Заметим, что порядок тайлов в руке не важен, и можно предполагать, что количество каждого типа тайлов, которые она может взять, неограничено.
Примечание
В первом примере у Tokitsukaze уже есть shuntsu.
Во втором примере у Tokitsukaze уже есть koutsu.
В третьем примере Tokitsukaze может собрать shuntsu, если возьмет один тайл — 1p или 4p. Тогда список тайлов в ее руке будет [3p, 9m, 2p, 1p] или [3p, 9m, 2p, 4p].