Xiao Q is a player who has just started learning Mahjong. He hopes to improve his skills through practice; however, his friends have all quit because they could not stand the torture of bad luck, leaving Xiao Q to practice alone.

In Mahjong, each player has 13 tiles in their hand. Each turn, the player draws one tile. If the 14 tiles form a winning hand, the player wins the round; otherwise, they must discard one tile and wait for the next draw.

To simplify the problem, we assume there are only 3 suits: Man (m), Pin (p), and Sou (s). Each suit has numbers 1–9, and there are 4 of each specific tile. We represent a hand as a string of numbers followed by 'm', a string of numbers followed by 'p', and a string of numbers followed by 's'. For example, a hand containing one each of 4, 5, 6 Man, two 9 Man, one each of 4, 5 Pin, and two each of 7, 8, 9 Sou (13 tiles in total) can be uniquely abbreviated as 45699m45p778899s.

A winning hand consists of 4 "sets" and 1 "pair", or 7 "pairs".

• A "set" is defined as:
  • 3 tiles of the same suit with consecutive numbers.
  • Or 3 tiles of the same suit with the same number.
• A "pair" is defined as:
  • 2 tiles of the same suit with the same number.

Note that each of the 14 tiles can only be used as part of one set or one pair. Taking 11123456789999m as an example, this is a winning hand because it can be decomposed into 4 sets: {123m}, {456m}, {789m}, {999m} and 1 pair: {11m}. If a 13-tile hand can become a winning hand after drawing one additional tile, we say the hand is "ready" (Tenpai).

Two special conditions:

• The tile needed to complete the hand must be possible to exist. For example, if a hand contains four 1s and can only win by drawing another 1s, it is not considered "ready" (because there are only 4 of each tile in total).
• When forming 7 pairs, the 7 pairs cannot contain duplicates. For example, 11112233445566s is not a winning hand (because it contains duplicate 1s pairs).

Xiao Q now has a 13-tile hand. He wants to know the minimum number of draw-and-discard cycles required to reach a "ready" state. Note that during the process of drawing and discarding, the hand must always be legal, meaning the count of any specific tile cannot exceed 4.

Input

The input consists of a single line containing a 16-character string, guaranteed to be in the format: a string of numbers followed by 'm', a string of numbers followed by 'p', and a string of numbers followed by 's'. Tiles of the same suit are given in ascending order. It is guaranteed that the hand is legal, meaning there are no more than 4 of any specific tile.

Output

Output a single integer representing the minimum number of draw-and-discard cycles required to reach a "ready" state. If the hand is already "ready", output 0.

Examples

Input 1

45699m45p778899s

Output 1

0

Input 2

45699m45p777889s

Output 2

1

Input 3

445699m245p7889s

Output 3

2

Input 4

44556m2449p3334s

Output 4

2

Input 5

11m11115599p559s

Output 5

2

Subtasks

Subtask 1 (10'): Guaranteed answer $\le 1$.

Subtask 2 (15'): Guaranteed answer $\le 2$.

Subtask 3 (25'): Guaranteed answer $\le 3$.

Subtask 4 (30'): Guaranteed answer $\le 4$.

Subtask 5 (20'): Guaranteed answer $\le 5$.