Cho một số nguyên dương ~N~. Ta thực hiện thao tác thay đổi các chữ số của ~N~ theo quy tắc sau:

• Chọn một vị trí bất kỳ trong chuỗi chữ số của ~N~.

• Thay thế chữ số tại vị trí đó bằng một chữ số mới (từ 0 đến 9).

• Điều kiện: Số mới được tạo thành phải có cùng số lượng chữ số với ~N~ và không được có chữ số 0 ở đầu.

Mỗi lần thay đổi một vị trí được tính là một thao tác.

Yêu cầu: Hãy tìm số thao tác tối thiểu để biến đổi số ~N~ ban đầu thành một số mới là bội của 111.

Input

• Dòng 1: số nguyên ~T~ ~(1 \le T \le 25)~ là số lượng bộ dữ liệu.

• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~N~.

Output

Gồm ~T~ dòng tương ứng với kết quả của ~T~ bộ dữ liệu. Mỗi dòng là một số nguyên đại diện cho số thao tác tối thiểu tìm được hoặc -1 nếu không có phương án thỏa mãn.

Scoring

Sample Input 1

4
111
220
13
991990

Sample Output 1

0
1
-1
2

Notes

Có 4 bộ dữ liệu:

• Số 111 không cần biến đổi.

• Số 220 không chia hết cho 111. Ta có thể thay chữ số 0 ở cuối thành chữ số 2 để được số 222 chia hết cho 111.

• Số 13 không thể biến đổi để chia hết cho 111.

• Số 991990 cần biến đổi hai chữ số ở vị trí 3 và vị trí 6 để được số 999999 chia hết cho 111.