You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Q 是一个刚接触麻将的玩家，他希望通过练习来提高自己的麻将水平，然而他的朋友纷纷因为受不了坏运气的折磨而退坑了，小 Q 只能自己一个人练习。

在麻将中，每个玩家拥有 13 张手牌。每一轮，他会摸一张牌，如果这 14 张手牌组成的牌型和了，就能宣告拿下这一局，否则他将打出一张手牌并期待下一次摸牌。

为简化题目，这里假设牌只分为 3 种花色：万子、饼子和索子，分别用字母 'm'、'p'、's' 表示（这里去掉了字牌）。每类牌都有数字 $1\sim 9$，每种数牌都有 4 张。我们用一串数字+'m'+一串数字+'p'+一串数字+'s'来表示一副手牌，比如一副含有 456 万各一枚、两枚 9 万、45 饼各一枚、789 索各两枚（共计 13 张）的手牌就可以唯一地简写为 45699m45p778899s。

一副牌和了的条件如下：手里 14 张牌能够组成 4 个"面子"和 1 个"雀头"，或者 7 个"对子"。

"面子"的定义为：

• 3 张同种花色、数字连续的牌。
• 或者 3 张同种花色、同样数字的牌。

"雀头"和"对子"的定义为：

• 2 张同种花色、同样数字的牌。

注意 14 张牌中的每一张牌只能用作一个面子或一个雀头的一部分。以牌 11123456789999m 为例，这副牌就是一副已经和了的牌，因为其能够拆解成 14 个面子：123m,456m,789m,999m 和一个雀头：11m。如果某副 13 张的手牌在加入另一张牌之后就能够和了，我们称这副 13 张的手牌"听牌"了。

两种特殊情况：

1. 所听的牌必须有可能存在，比如一副手牌如果包含 4 张 1s ，且只有再加入一张 1s 后才能和牌，那这副手牌不算做听牌状态（因为 1s 总共只有 4 张）。
2. 做 7 对子时，7 个对子中不能有重复的，比如 11112233445577s 并不算一副和了的手牌（因为包含了重复的 1s 对子）。

现在小 Q 得到了一副 13 张手牌，他想要知道这副牌最少需要经过多少次摸牌、打出牌，才能够进入听牌的状态。注意，在摸牌、打牌的过程中，小 Q 的手牌必须始终是合法的，即其中任意牌的数量不能超过 4 张。

输入格式

输入包含 1 行，一个长为 16 个字符的字符串，保证格式为：一串数字+'m'+一串数字+'p'+一串数字+'s'。

同种花色的牌按数字从小到大给出。保证这副牌是合法的，即同样花色同样数字的牌不会超过 4 张。

输出格式

输出包含 1 行，一个整数表示这副牌最少需要经过多少次摸牌、打出牌，才能够进入听牌的状态。如果已经听牌则输出 0。

数据范围

保证答案小于等于五。

输入样例1：

45699m45p778899s

输出样例1：

0

输入样例2：

45699m45p777889s

输出样例2：

1

输入样例3：

445699m245p7889s

输出样例3：

2

输入样例4：

44556m2449p3334s

输出样例4：

2

输入样例5：

11m11115599p559s

输出样例5：

2