Програмчлалын олимпиадын бодлогын архив

Хэдэн жилийн турш аялсны эцэст худалдаачин Дорж төвхнөхөөр шийджээ. Тэр өөрийн үйлчлүүлэгчидтэйгээ аль болох ойр байхаар байшин барихаар болсон бөгөөд азаар тэр бүх үйлчлүүлэгчдийнхээ байрлалыг мэддэг байжээ. Түүний бүх үйлчлүүлэгчид ялгаатай бүхэл тоон координаттай цэгүүдэд байрлана. Доржын барих байшин нь бүхэл тоон координатад баригдах бөгөөд аль ч үйлчлүүлэгчийн байрлалтай давхцахгүй байх ёстой. Дорж том бөгөөд хүн амын нягтаршил ихтэй хотод амьдарч буй тул шинэ баригдах байшин ба i-р хэрэглэгчийн хоорондын зай нь |x − x_i| + |y − y_i| томъёогоор тодорхойлогдоно.
Бүх хэрэглэгч хүртэлх зайн нийлбэр нь хамгийн бага байхаар Доржийн төвхнөх нийт боломжит байрлалын тоог ол.

Input

Эхний мөрөнд тестийн тоо t ( 1 ≤ t ≤ 100 ). Үүний дараа тест бүр нь дараах байдалтай байна.
• Нэг мөрөнд Доржийн хэрэглэгчдийн тоо нь n (1 ≤ n ≤ 2000) байна.
• x_i болон y_i (−1000000000 ≤ x_i, y_i ≤ 1000000000) тоонуудыг агуулах n ширхэг мөр байна.

Output

Тест бүрийн хувьд:
• Бүх хэрэглэгч хүртэлх зайн нийлбэрийн хамгийн бага утга ба нийт боломжит байрлалын тоо.

Example

Input:
2
4
1 -3
0 1
-2 1
1 -1
2
-999888777 1000000000
1000000000 -987654321


Output:
10 4
3987543098 3975087573110998514