该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

Turn all the lights on!

Timothy planned to hold an awards ceremony after the race. To enhance the atmosphere, he prepared a garland of four colored light bulbs, with the color of the $i$th bulb being $S_i$.

Initially, all the light bulbs are off. Your task is to turn them all on. You can perform this operation any number of times: select a light bulb and toggle its state (if off, turn it on; if on, turn it off). However, you must only perform an operation on a light bulb if the state of the bulb you toggled is different from the previous one (and you can choose any bulb for the first operation). For example, if you chose color $a$ the first time, you cannot choose $a$ the second time, but you can choose $a$ the third time.

Calculate the minimum number of operations required to turn all the light bulbs on. If this is not possible, output $-1$.

Input

The first line of input contains an integer $t$ ($1 \leq t \leq 10^4$), representing the number of test cases.

The next $t$ lines each contain a string $s$ of length 4, where each character is a decimal digit representing the color of the corresponding light bulb.

Output

Output an integer representing the minimum number of operations, or $-1$ if this is not possible.

Sample

3
9546
0000
3313

4
-1
6

Notes

For the first example, 9546 (all colors are different): 4 operations (directly turn on each bulb);

For the second example, 0000 (all colors are the same): impossible (no further operation after one operation), output -1;

For the third example, 3313 (the color distribution is 3 3s and 1 1): 6 operations are required (achieved through alternating operations).

For other examples, please scan the QR code below after the competition to view them.

Please use pdf to scan the QR code!