Thành phố XY có một mạng lưới các đường hai chiều với các thuộc tính sau:

1. Không có nhiều hơn một con đường giữa mỗi cặp nút giao thông.
2. Một nút giao thông được kết nối với mọi nút giao thông khác bằng một đường nối trực tiếp hoặc qua một số nút giao thông.
3. Khi đèn được đặt ở một nút giao thông, tất cả con đường nối trực tiếp với nút giao thông đó đều sáng.

Yêu cầu:

1. Tìm số lượng nút giao thông ít nhất để đặt đèn sao cho khi tất cả đèn được thắp sáng thì tất cả con đường cũng được thắp sáng.
2. Tìm số cách để đặt đèn lên các nút giao thông sao cho số lượng nút giao thông được đặt đèn là nhỏ nhất và tất cả các con đường đều được thắp sáng.

Dữ liệu vào

• Dòng đầu tiên là số nguyên dương ~ t ~, cho biết số test.
• Mỗi test có cấu trúc như sau:
  • Dòng đầu tiên chứa số nguyên dương ~ n ~ biểu thị số lượng nút giao thông. Mỗi nút giao thông được đánh một số nguyên từ 1 đến ~ n ~.
  • ~ n-1 ~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~ u, v ~ ( 1 ≤ u, v ≤ n ) cho biết có một đường nối trực tiếp từ nút ~ u ~ đến nút ~ v ~.

Kết quả

Gồm ~ t ~ dòng, dòng thứ ~ i ~ tương ứng trả lời cho test thứ ~ i ~ trong dữ liệu vào. Mỗi dòng gồm hai số nguyên, số thứ nhất trả lời cho yêu cầu thứ nhất, số thứ hai trả lời cho yêu cầu thứ hai. Vì số thứ hai có thể quá lớn nên được lấy dư cho 10007.

Ràng buộc

• ~1≤t≤20~
• ~1≤n≤100100~

Ví dụ:

Input 1

2
4
1 2
2 3
3 4
3
1 2
1 3 

Output 1

2 3
1 1