Trong một vương quốc, có các phòng giam (được đánh số từ 1 đến \(P\)) được xây dựng tạo thành một đoạn thẳng. Các phòng số \(i\) và \(i+1\) nằm cạnh nhau, và các tù nhân ở các phòng cạnh nhau được gọi là "hàng xóm". Một bức tường có cửa sổ ngăn cách các phòng cạnh nhau, và hàng xóm có thể giao tiếp qua cửa sổ đó.

Tất cả tù nhân sống trong hòa bình cho đến khi một tù nhân được thả. Khi điều đó xảy ra, những người hàng xóm của tù nhân được thả sẽ biết tin, và mỗi người lại truyền tin này cho hàng xóm khác của mình. Tù nhân đó lại truyền tiếp cho hàng xóm khác của anh ta, và cứ thế cho đến khi tin tức chạm đến một tù nhân không còn hàng xóm nào khác (vì anh ta ở phòng 1, hoặc phòng \(P\), hoặc phòng bên cạnh đang trống). Một tù nhân khi phát hiện ra một tù nhân khác đã được thả sẽ tức giận đập phá mọi thứ trong phòng mình, trừ khi anh ta được hối lộ bằng một đồng tiền vàng. Vì vậy, sau khi thả một tù nhân ở phòng \(A\), tất cả các tù nhân đang ở hai bên phòng \(A\) - cho đến phòng 1, phòng \(P\) hoặc một phòng trống - cần phải được hối lộ.

Giả sử rằng mỗi phòng giam ban đầu có đúng một tù nhân, và mỗi ngày chỉ có thể thả một tù nhân. Cho danh sách \(Q\) tù nhân sẽ được thả trong \(Q\) ngày, hãy tìm tổng số đồng tiền vàng tối thiểu cần dùng để hối lộ nếu các tù nhân có thể được thả theo bất kỳ thứ tự nào.

Lưu ý rằng mỗi lần hối lộ chỉ có tác dụng trong một ngày. Nếu một tù nhân đã được hối lộ hôm qua nghe tin về một tù nhân khác được thả hôm nay, anh ta cần phải được hối lộ lần nữa.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\). \(N\) bộ test theo sau. Mỗi bộ test gồm 2 dòng.
Dòng đầu tiên có định dạng:

P Q

Dữ liệu ra

Với mỗi bộ test, xuất một dòng có định dạng:

Case #X: C

Ràng buộc

• \(1 \le N \le 100\)
• \(Q \le P\)
• Mỗi số phòng nằm trong khoảng từ 1 đến \(P\), bao gồm cả hai đầu.

Phân nhóm

• Small dataset:

  • \(1 \le P \le 100\)
  • \(1 \le Q \le 5\)

  • Large dataset:

  • \(1 \le P \le 10000\)

  • \(1 \le Q \le 100\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
8 1
3
20 3
3 6 14

Case #1: 7
Case #2: 35

Nguồn

Google Code Jam 2009, Vòng 1C, bài Bribe the Prisoners.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.