Background

 MS is a very NB teammate of Legendary Grandmaster DiDiDi. There are endless stories about how they won the championship in various Grand Prix.

 One day after they get the championship in GP of Zhijiang, MS goes to Zhijiang food street to find something to eat tonight.

 After visiting every food shop in the street, he found a ”Jansou” owned by fuko_ibuki in the corner, where one could play mahjong.

 There are $34$ different tiles in Majong, which can be divided into four suits: Manzu , Souzu , Pinzu , and Jihai . Manzu, Souzu, and Pinzu each have 9 kinds of tiles, and Jihai only has 7 kinds of tiles.

 Here are the pictures of tiles, each row represents a suit - Manzu, Souzu, Pinzu, and Jihai. To simplify the expression, we use **number ** + suit to represent a tile. For example, ”1m” stands for Wanzu of 1, ”4s” stands for Souzu of 4, ”7p” stands for Pinzu of 7, and Jihai are numbered in the order of the picture above, such as ”4z” for North Wind.

 Mahjong starts with what we call a ”hand” of $13$ tiles, and with each turn, the player draws a new tile and discards one.

 A complete hand has $14$ tiles, consisting of seven different Toitsu or four Mentsu plus a Toitsu, where Toitsu refers to two tiles of the same suit with the same number, and Mentsu includes Shuntsu and Koutsu. Shuntsuis three consecutive cards of the same suit (not including Jihai, and cannot be cycled), and Koutsuis three cards of the same suit with the same number.

 For example, $1m2m3m$ is Shuntsu (abbreviated as $123m$), $1z2z3z$ and 8m9m1m are not Shuntsu, $1m1m1m$ is Koutsu, and $1z1z1z$ is also Koutsu. And $123m789m 111s 789s 99p$ makes a complete hand.

 We call a hand Tenpai , that is, it has $13$ tiles, and a complete hand can be achieved by drawing one tile.

 For example, $123m 789m 111s 78s 99p$ can achieve complete hand by drawing $6p$ or $9p$ (or awaiting $6p$ and $9p$ in short). So this hand is Tenpai.

 In the process of learning mahjong, MS learns the concept of X-Shanten , in which ”X”represents the minimum number of rounds for a player to draw and discard tiles to achieve Tenpai. Since there are two ways to achieve the complete hand, we choose the one that is closer to the two types.

 For example, $13p 567p 245s 77s 11z 3z$ can draw $2p$ and discard $3z$ to become $123p 567p 245s 77s 11z$, and draw $7s$ and discard $2s$ to become $123p 567p 45s 777s 11z$, which is Tenpai to awaiting $3s$ and $6s$, so this hand ($13p 567p 245s 77s 11z 3z$) is $2$-Shanten.

 Since $7$ pairs can also achieve the complete hand, the maximum number of ”x” is $6$ (because we can change $6$ tiles to pairs to achieve the Tenpai), otherwise, $147m 258s 369p 1234z$ is ”8-Shanten”.

 we define Taatsu as $2$ tiles awaiting one to achieve a Mentsu, such as $46s, 45s,$ and $55s,$ and each tile could only be contained in one Taatsu. A simple way to calculate the ”x-Shanten” is $x = 8$ - (Mentsu * $2$ + Taatsu), but be careful in the case when you have $6$ or more Taatsu.

 fuko_ibuki gives MS n different hands, and MS needs to tell her the hand is X-Shanten. To simplify the input, we use xxxx $m$ xxxx $s$ xxxx $p$ xxxx $z$ to give a hand (or leave out if there is no tile of the suit), like $123m 456m 123s 789s 44z$ would be represented as $123456m123789s44z$.

Input

The first line contains an integer $T ( T ≤ 5000)$, denoting the number of test cases. For each test case, the only line contains a ”hand” described above.

Output

For each test case, print one integer n in one line, denoting the x of ”x-Shanten”.

Samples

2
24577s13567p113z
33446m88s5599p12z

2
1