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

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

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

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

• "面子"的定义为：
  • 3张同种花色、数字连续的牌
  • 或者3张同种花色、同样数字的牌
• "雀头"和"对子"的定义为：
  • 2张同种花色、同样数字的牌

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

两种特殊情况：

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

子任务

subtask1 (10'): 保证答案<=1。

subtask2 (15'): 保证答案<=2。

subtask3 (25'): 保证答案<=3。

subtask4 (30'): 保证答案<=4。

subtask2 (20'): 保证答案<=5。