Trò chơi miễn phí

Một vách đá cao $h$ đơn vị. Trên mỗi độ cao $x$ từ $1$ tới $h$ có đúng một bục di động, đang ở trạng thái ẩn (ở bên trong vách) hoặc đẩy ra (nhô ra ngoài). Ban đầu có $n$ bục đang đẩy ra ở các độ cao $p_1,p_2,\dots ,p_n$ (với $h=p_1>p_2>\cdots >p_n\ge 1$). Nhân vật đang đứng trên bục ở độ cao $h$.

Nếu nhân vật đang đứng ở độ cao $x$ (bục $x$ đang đẩy ra), nó có thể kéo cần gạt: bục $x$ sẽ chuyển sang trạng thái ẩn, đồng thời bục ở độ cao $x-1$ đảo trạng thái (đẩy ra $\to$ ẩn hoặc ẩn $\to$ đẩy ra). Đây là cách duy nhất để di chuyển giữa các bục.

Nhân vật rất mỏng manh: nó chỉ sống sót khi rơi tối đa $2$ đơn vị. Tức là rơi từ $x$ xuống bục $x-1$ hoặc $x-2$ là an toàn, còn rơi tới $x-3$ trở xuống (mà chưa được bục nào đỡ) là chết.

Nhân vật có thể mua các viên pha lê ma thuật. Mỗi viên cho phép đảo trạng thái của một bục bất kỳ, trừ bục ở độ cao $h$. Mỗi viên chỉ dùng được một lần.

Hỏi số viên pha lê tối thiểu cần mua để nhân vật đáp xuống mặt đất (độ cao $0$) an toàn.

Dữ liệu vào

• Dòng đầu chứa số nguyên $q$ — số truy vấn.
• Mỗi truy vấn gồm hai dòng:
  • Dòng thứ nhất chứa hai số nguyên $h$ và $n$.
  • Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$ theo thứ tự giảm dần.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên — số viên pha lê tối thiểu cần dùng.

Ràng buộc

• $1\le q\le 100$
• $1\le h\le {10}^9$
• $1\le n\le min(h,2·{10}^5)$
• $h=p_1>p_2>\cdots >p_n\ge 1$
• Tổng $n$ trên tất cả các truy vấn không vượt quá $2·{10}^5$.

Ví dụ