Xếp hình

Xếp hình là một trong những trò kinh điển thời tuổi thơ dữ dội của chúng ta. Trò chơi gồm một bảng $3\times 3$ chứa $8$ miếng ghép và một ô trống. Người chơi cố gắng sắp xếp lại các miếng ghép thành một thứ tự định sẵn, bằng cách lặp lại việc di chuyển một trong các miếng ghép kề cạnh với ô trống vào ô trống (và dĩ nhiên ô trống sẽ chuyển sang vị trí của miếng ghép). Để đơn giản, các miếng ghép được đánh số từ $1$ đến $8$ và thứ tự định sẵn như sau: ô trống nằm ở góc trên bên trái, hàng trên cùng là ô trống, $1$, $2$; hàng giữa là $3$, $4$, $5$; hàng dưới cùng là $6$, $7$, $8$:

Ở phiên bản khó của trò chơi, bạn cần tìm số bước di chuyển ít nhất để đưa trạng thái đã cho về trạng thái định sẵn. Hùng đã chơi trò này nhiều lần nhưng vẫn gặp vấn đề với phiên bản khó, và có vẻ bài tập này được thiết kế để dành riêng cho cậu.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $T$ là số lượng testcase;
• $T$ dòng tiếp theo, mỗi dòng chứa $9$ số nguyên là một hoán vị của $0,1,2,\dots ,8$ mô tả một trạng thái bắt đầu. Các số trong hoán vị lần lượt là các số ghi trên các ô của bảng, theo thứ tự từ trái sang phải, từ trên xuống dưới. Số $0$ đại diện cho ô trống.

Như vậy trạng thái định sẵn ứng với hoán vị $012345678$.

Dữ liệu ra

Gồm $T$ dòng, mỗi dòng ghi một số nguyên là số bước di chuyển ít nhất, hoặc $-1$ nếu không thể đưa trạng thái này về trạng thái định sẵn.

Ràng buộc

• $1\le T\le {10}^6$.

Subtasks

• $30\%$ số test với $T=5$ và kết quả không vượt quá $10$;
• $30\%$ số test tiếp theo có kết quả không vượt quá $10$;
• $40\%$ số test tiếp theo với ràng buộc gốc.

Trong hai subtask đầu, "kết quả không vượt quá $10$" nghĩa là mọi trạng thái trong test đều đưa được về trạng thái định sẵn với không quá $10$ bước (không có đáp án $-1$).

Ví dụ