Koi có một chiếc Rubik 2x2. Rảnh rỗi sinh nông nổi: Cậu bóc hết miếng dán màu trên Rubik ra và tô lại mỗi khối góc bằng một màu, các màu đôi một phân biệt. Cậu rất thích thú và tự gọi đây là "Koibik".

Koi nhìn cố định một mặt trước của khối, cậu xác định trạng thái của Koibik băng một bộ 8 phần tử \((a, b, c, d, e, f, g, h)\) với:

\(a\) là màu của góc: mặt trước, tầng trên, bên phải.

\(b\) là màu của góc: mặt sau, tầng trên, bên phải.

\(c\) là màu của góc: mặt sau, tầng trên, bên trái.

\(d\) là màu của góc: mặt trước, tầng trên, bên trái.

\(e\) là màu của góc: mặt trước, tầng dưới, bên phải.

\(f\) là màu của góc: mặt sau, tầng dưới, bên phải.

\(g\) là màu của góc: mặt sau, tầng dưới, bên trái.

\(h\) là màu của góc: mặt trước, tầng dưới, bên trái.

Mỗi lần Koi chỉ có thể xoay một trong 6 mặt của Koibik một góc 90 độ cùng chiều hoặc ngược chiều kim đồng hồ.

Koi tự hỏi cần ít nhất bao nhiêu lần xoay để từ một trạng thái này của Koibik chuyển sang trạng thái kia? Các bạn hãy lập trình giúp Koi giải bài toán này nhé.

Đầu vào

Dòng đầu là trạng thái ban đầu của Koibik.

Dòng thứ hai là trạng thái cuối của Koibik.

Ghi chú: Mỗi trạng thái gồm 8 chữ cái đôi một phân biệt viết liền nhau và các trạng thái là hoán vị của nhau.

Đầu ra

Số tự nhiên duy nhất là kết quả của bài toán, nếu không có cách nào để chuyển về trạng thái cuối xuất ra -1.

Ví dụ

Đầu vào:

abcdefgh
dabcefgh

Đầu ra:

1