Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Ngày tết thiếu nhi năm nay, tổ dân phố X mời một đoàn xiếc về biểu diễn. Một trong các tiết mục đặc sắc và được các bạn nhỏ yêu thích đó là màn xiếc thú với k con khỉ biểu diễn trên sân khấu. Sàn sân khấu có dạng một lưới ô vuông kích thước n × m, được chia bởi  n+1 đường dọc và m+1 đường ngang. Các đường dọc được gán toạ độ theo cột từ 0 đến n, từ trái sang phải, còn các đường ngang được gán toạ độ theo dòng từ 0 đến m, từ dưới lên trên. Giao điểm giữa đường dọc x và đường ngang y có toạ độ (x, y). Khi biểu diễn, mỗi con khỉ sẽ di chuyển theo một hành trình nhất định, con khỉ thứ i sẽ di chuyển theo hành trình gồm các đoạn thẳng nối hai điểm liên tiếp trên lưới lần lượt qua các điểm

(xi,1, yi,1), (xi,2, yi,2), …, (xi,r(i), yi,r(i)),

trong đó r(i) là số điểm trên hành trình của con khỉ i. Để tránh xung đột khi biểu diễn, các đoạn thẳng nối trên hành trình của con khỉ i sẽ không có điểm chung với bất cứ đoạn thẳng nào trên hành trình của con khỉ j (i ≠ j). Hơn nữa, để các con khỉ di chuyển đúng theo hành trình và trang hoàng sân khấu, nghệ sĩ xiếc thú đã tiến hành tô màu các vùng liên thông trên sàn sân khấu được tạo ra từ các đoạn thẳng nối trên các hành trình của k con khỉ và các đường biên của sân khấu, mỗi một vùng sẽ được tô bằng một màu và không có hai vùng nào bị tô bởi cùng một màu.

Yêu cầu: Cho kích thước sàn sân khấu và hành trình của k con khỉ. Hãy tính số màu cần dùng để tô màu các vùng liên thông trên sàn sân khấu được tạo ra từ các đoạn thẳng nối trên các hành trình của k con khỉ và các đường biên của sân khấu.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không vượt quá 10 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Mỗi bộ dữ liệu gồm một nhóm dòng có khuôn dạng:

• Dòng đầu tiên ghi ba số nguyên dương n, m và k (n, m ≤ 10⁶ ; k ≤ 1000);
• Dòng thứ i trong số k dòng tiếp theo mô tả hành trình của con khỉ thứ i (i = 1, 2, ..., k): số đầu tiên của dòng là số r(i) (r(i) ≤ 50); tiếp theo là r(i) cặp số nguyên dương x_i,j, y_i,j (0 < x_i,j < n,   0 < y_i,j < m, j = 1, 2, …, r(i)).

Output

Với mỗi bộ dữ liệu, ghi ra trên một dòng một số là số lượng màu cần dùng.

Example

Input:
1
6 5 2
5 2 2 2 3 3 3 3 2 2 2
8 1 1 1 4 4 4 4 1 1 1 2 1 5 2 3 4

Output:
6