"Vương quốc Byteland có $N$ thành phố được đánh số từ $0$ đến $N-1$. Giữa các thành phố có $M$ con đường hai chiều được đánh số từ $0$ đến $M-1$. Có $K$ cổng dịch chuyển......"

Đang mơ tưởng về một đề bài nữa để gieo rắc đau đớn và làm khổ các học sinh CP trên toàn thế giới, đức vua của vương quốc Byteland bỗng nhận được thông báo rằng: Các thành phố trong vương quốc Byteland, do đã quá lâu mà không có input gì từ nhà vua (do quý ngài đáng kính của chúng ta đã không làm việc gì ngoài mõm ra các task được $10^9+7$ năm rồi) nên đã sắp sửa đánh nhau ầm ầm đến nơi. Mọi chuyện có vẻ không ổn lắm.

Ở vương quốc Byteland hiện tại vẫn có $N$ thành phố - được đánh số từ $1$ đến $N$. Trước đây, giữa các thành phố đều có quan hệ tương đối tốt đẹp với nhau. Tuy nhiên, sau whatever năm phải chịu đựng sự "hữu dụng" của quý ngài problemsetter cho các bài từ IOI đến Codeforces, từ POI đến APIO, cả vương quốc đã bắt đầu tôn thờ $1$ vị thần số học. Vì $1$ lí do nào đó (chắc chắn không phải là do thằng ra đề muốn thế), giữa $2$ thành phố được đánh số $i$ và $j$, nếu giá trị $i*j$ là số chính phương, mức độ xung đột giữa $2$ thành phố này sẽ tự dưng vô cùng bùng nổ và tất cả người dân ở $2$ thành phố này đều sẽ cảm thấy như thể cái bọn đến từ thành phố còn lại đã tàn sát cả họ nhà mình vậy. Còn không thì bình thường, không có chuyện gì cả.

Bỗng dưng tỉnh ngộ sau whatever năm chỉ ngồi code mõm, nhà vua muốn biết rằng: Có bao nhiêu cặp thành phố $i, j$ $(1 \le i < j \le N)$ mà giữa $2$ thành phố này không có xung đột với nhau.

Tùy vào mức độ không-vô-trách-nhiệm của mình, nhà vua có thể sẵn sàng bỏ ra tận $Q$ ngày $(0 \le Q \le 31)$ để vi hành quanh vương quốc (và tận mắt chứng kiến hậu quả của những hành động của mình). Do ngân sách nhà nước gần như đã không còn, để di chuyển giữa 2 thành phố, nhà vua bắt buộc phải sử dụng các cây cầu vốn đã có sẵn, nối giữa mọi cặp $2$ thành phố $(i, j)$ $(1 \le i < j \le N)$. Dù đã xuống cấp trầm trọng, phần lớn những cây cầu vẫn còn có thể đi được. Tuy nhiên, mọi cây cầu kết nối 2 thành phố bị xung đột với nhau đều đã bị phá hủy.

Trong tình hình nguy cấp và tệ hại như vậy, nhà vua muốn xây dựng hành trình cho chuyến vi hành của mình trong mỗi ngày thỏa mãn các điều kiện sau:

• Trong $1$ chuyến vi hành, không có thành phố nào được đi qua nhiều hơn $1$ lần.
• Chỉ sử dụng các cây cầu vẫn còn có thể đi được - nghĩa là, nếu ở bước thứ $A$ đang ở thành phố $B$ thì ở bước thứ $A+1$ không được phép ở $1$ trong các thành phố đang có xung đột với thành phố $B$.
• Nhà vua sẽ ưu tiên đi thăm các thành phố có xung đột với thành phố hiện tại sớm nhất có thể: Nếu bước thứ $A$ của đường đi đi qua thành phố $B$, bước thứ $A+2$ phải đi qua $1$ trong số các thành phố có xung đột với thành phố $B$ mà chưa đi qua (nếu nó có tồn tại). Nếu đến bước thứ $A$ mà không còn thành phố nào xung đột với thành phố đang đi qua nữa, ở bước thứ A+2 đi đến đâu cũng được (dĩ nhiên, phải thỏa mãn tất cả các điều kiện đã nêu ra ở trên.
• Tuy có mong muốn sẽ có thể hòa giải xung đột giữa các cặp thành phố nếu có thể, nhà vua không muốn cố quá để rồi thành quá cố. Cụ thể hơn, trong chuyến vi hành ở ngày thứ $Q$ (mà ta đang xét đến), không tồn tại $1$ nhóm $K+1$ thành phố đôi một không có xung đột với nhau.
• Ở mỗi ngày, sẽ có $C$ thành phố quan trọng - sắp xảy ra bạo loạn. Đường đi bắt buộc phải đi qua tất cả $C$ thành phố này.
• Số thành phố mà đường đi đi qua là lớn nhất có thể.

Yêu cầu: Với mỗi câu hỏi của nhà vua, in ra câu trả lời tương ứng.

5
3 
1 0
2 2
3 5
2 1
3

9
1
2
3

12
2
3 0
3 1
5

61
7
6