Bedao Regular Contest 02 - 8ROOKS

Xem dạng PDF

Gửi bài giải


Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Sau khi xem bộ phim "Queen's Gambit", Copium tập tành chơi cờ vua nhưng khổ nỗi không ai muốn chơi cờ với Copium cả, vì vậy Copium thường tự chơi với bàn cờ ~8 \times 8~ của mình. Trên bàn cờ của Copium có ~8~ quân xe và được xếp sao cho mỗi cột có đúng ~1~ quân xe, tuy vậy bàn cờ ban đầu không đàm bảo các quân xe không ăn nhau thế nên Copium cần xếp lại bàn cờ của mình để đảm bảo không quân xe nào ăn được nhau ( ~2~ quân xe có thể ăn nhau nếu thuộc cùng hàng hoặc cùng cột ). Ở mỗi thao tác, Copium được chọn một quân xe đang đứng ở ô ~(i,j)~ bất kì và di chuyển nó theo ~1~ trong ~2~ cách sau:

  • Lùi lại ~k~ bước, mỗi bước đi từ ô ~(i, j)~ đang đứng đến ô ~(i-1, j)~ nếu ~i > 1~ hoặc ô ~(8, j)~ nếu ~i = 1~.
  • Tiến lên ~k~ bước, mỗi bước đi từ ô ~(i, j)~ đang đứng đến ô ~(i+1, j)~ nếu ~i < 8~ hoặc ô ~(1, j)~ nếu ~i = 8~.

Giỏi chơi cờ là thế nhưng về những khoản tính toán như này Copium hơi kém, thế nên Copium đã soạn trước ~Q~ câu hỏi, ứng với mỗi câu hỏi Copium cho bạn biết được trạng thái của bàn cờ và số ~k~, vì vậy Copium cần biết số thao tác ít nhất để xếp lại bàn cờ sao cho thỏa mãn yêu cầu.

Input

  • Dòng đầu tiên là số ~Q~ ~( 1 \leq Q \leq 10^6 )~ thể hiện cho số câu hỏi của Copium và số ~k~ ~(1 \leq k \leq 10^9)~
  • Dòng thứ hai gồm ~Q~ chuỗi ~8~ chữ số, mỗi chữ số có giá trị từ ~1~ đến ~8~ đại diện cho vị trí các quân xe ở ~8~ cột

Output

  • In ra ~Q~ dòng tiếp theo, mỗi dòng là số thao tác ít nhất cần di chuyển các quân xe sao cho thỏa mãn yêu cầu, in ra ~-1~ nếu không có cách xếp thỏa mãn.

Sample Input

3 2
12345672 17234568 11111111

Sample Output

1 
0
-1

Sample Input

2 1
11111111 12121212

Sample Output

16
12

Subtask

  • ~30\%~ số test có ~1 \leq Q \leq 10~.
  • ~20\%~ số test có ~ k = 1 ~.
  • ~50\%~ số test còn lại không có ràng buộc gì thêm.

Note


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.