Có một con mèo, \(k\) con chuột và một cái hang chuột trên một trục tọa độ Ox. Con mèo nằm ở điểm 0, cái hang nằm ở điểm \(n\). Tất cả các con chuột nằm giữa con mèo và cái hang: con chuột thứ \(i\) nằm ở điểm \(x_{i}\) (\(0 < x_{i} < n\)). Tại mỗi điểm có thể có nhiều con chuột.

Trong một giây, những điều sau đây sẽ thực hiện liên tục:

+ Đầu tiên, có đúng một con chuột di chuyển sang bên phải 1 đơn vị. Nếu con chuột đến hang, nó sẽ trốn được mèo (tức là con chuột sẽ không di chuyển đến bất kỳ điểm nào nữa và sẽ không bị con mèo ăn thịt).

+ Sau khi chuột di chuyển xong mèo di chuyển sang phải 1 đơn vị. Nếu ở vị trí mới của mèo có chuột, mèo sẽ ăn thịt chúng (những con chuột bị ăn thịt sẽ loại ra khỏi trục số).

+ Các hoạt động của mèo và chuột sẽ kết thúc khi mèo đến được vị trí \(n\) (tất nhiên những con chuột trốn trong hang tại vị trí \(n\) sẽ không bị ăn thịt).

Mỗi giây, bạn có thể chọn một con chuột sẽ di chuyển. Hỏi tối đa bao nhiêu con chuột lọt được vào hang mà không bị ăn thịt?

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên dương \(t\) (\(1 \leq t \leq 10\)) là số lượng bộ test. Mỗi bộ test sẽ có dạng như sau:

+ Dòng đầu tiên chứa số nguyên \(n\) và \(k\) (\(1 \leq n \leq 10^{9};\ 1\ \leq k \leq 5*10^{5}\))

+ Dòng thứ hai chứa \(n\) số nguyên \(x_{1},\ x_{2},\ \ldots,\ x_{k}\) (\(1 \leq x_{i} < n\)) là vị trí của các con chuột.

Kết quả:

+ Gồm \(t\) dòng, mỗi dòng chứa một giá trị \(P\) là số lượng những con chuột đã trốn vào hang tương ứng với dữ liệu đầu vào.

Ví dụ:

Ràng buộc:

• Subtask 1: Có 20% số test đầu tiên \(k = 2\)

• Subtask 2: Có 30% số test tiếp theo \(n \leq 500,\ k \leq 10000\)

• Subtask 3: Có 50% số test cuối cùng không có ràng buộc gì