#584 67

Statement

Statement language

You are given a decimal number $S$ of length $N$ .

You may delete some characters from $S$ . The relative order of the remaining characters does not change. At least one character must remain.

The number formed by the remaining characters must be divisible by $6$ or by $7$ . Find the minimum number of characters to delete. If this is impossible, print $-1$ .

The resulting string may begin with $0$ . For example, $\texttt{007}$ represents the decimal number $7$ . The number $0$ is divisible by both $6$ and $7$ .

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum number of characters to delete on one line. If it is impossible, print $-1$ .

Constraints

$1 \leq T \leq 200\,000$ .
$1 \leq N \leq 200\,000$ .
The first character of $S$ is not , and every character is a digit.

Subtasks

#	Score	Constraints
1	17	$N \leq 10$ , and the sum of $N$ over all test cases is at most $5\,000$ .
2	29	$N \leq 1\,000$ , and the sum of over all test cases is at most .

Samples

Input

Output

In the first case, deleting the first $1$ produces $\texttt{007}$ . In the third case, no nonempty valid result exists.

In the fifth case, no deletion is needed. In the sixth case, deleting $1$ leaves $0$ .