Kamome สนใจการสังเกตดาวตกเป็นอย่างมาก เขาได้สร้างแบบจำลองสองมิติขนาดใหญ่ไม่จำกัดที่จำลองการเคลื่อนที่ของดาวตก (แม้ว่าจริง ๆ แล้วมันจะไม่ได้จำลองอะไรเลยก็ตาม) มีแบบจำลองดาวตก $n$ ดวงในการจำลองนี้ และน้ำหนักของแบบจำลองดาวตกดวงที่ $i$ คือ $m_i$ แบบจำลองดาวตกแต่ละดวงเคลื่อนที่ด้วยอัตราเร็วคงที่ไปตามเส้นตรงที่กำหนดไว้ (หรืออาจจะอยู่นิ่งก็ได้)

เวลาผ่านไปนานมากแล้วนับตั้งแต่ Kamome เริ่มรันแบบจำลองนี้ วันหนึ่ง Kamome เกิดความคิดขึ้นมาอย่างกะทันหันและได้ถ่ายภาพแบบจำลองปัจจุบันไว้สองภาพ โดยให้ตำแหน่งของ Kamome เป็นจุดกำเนิด สำหรับแต่ละภาพ $i$ ($i = 1, 2$) แบบจำลองดาวตกดวงที่ $j$ จะอยู่ที่ตำแหน่ง $(x_{i,j}, y_{i,j})$ บนระนาบ

คุณสามารถคำนวณวิถีการเคลื่อนที่ของแบบจำลองดาวตกแต่ละดวงได้ แต่นั่นยังไม่พอ! Kamome ต้องการให้คุณคำนวณสำหรับแบบจำลองดาวตก $i$ แต่ละดวงว่า แรงโน้มถ่วงสูงสุดที่แบบจำลองดาวตกดวงอื่นใด ๆ กระทำต่อมันตลอดช่วงเวลาทั้งหมดที่แบบจำลองนี้ทำงานอยู่มีค่าเท่าใด (คุณสามารถถือว่ามีเวลาไม่จำกัดทั้งก่อนและหลังการถ่ายภาพ)

สังเกตว่าสูตรแรงโน้มถ่วงปกติสามารถเขียนใหม่ได้เป็น $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$ เพื่อหลีกเลี่ยงการจัดการกับกรณีพิเศษบางประการ Kamome จึงให้ค่า $m'_i = \frac{1}{m_i}$ เป็นข้อมูลนำเข้าแทน และคุณเพียงแค่ต้องแสดงผลลัพธ์ของการนำคำตอบไปหารด้วย $G$ แล้วหาค่าส่วนกลับ กล่าวคือ สำหรับแต่ละ $i$ จงคำนวณค่า $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$ เมื่อ $D_t(i, j)$ คือระยะห่างระหว่างแบบจำลองดาวตก $i$ และ $j$ ณ เวลา $t$ และ $t$ สามารถเป็นจำนวนจริงใด ๆ ก็ได้ (ลบ, บวก หรือศูนย์)

ข้อมูลนำเข้า

แต่ละชุดการทดสอบประกอบด้วยหลายชุดทดสอบย่อย บรรทัดแรกประกอบด้วยจำนวนเต็ม $t$ ($1 \le t \le 10^4$) แทนจำนวนชุดทดสอบย่อย รายละเอียดของชุดทดสอบย่อยมีดังนี้

บรรทัดแรกประกอบด้วยจำนวนเต็มหนึ่งจำนวน $n$ ($2 \le n, \sum n \le 10^5$) แทนจำนวนแบบจำลองดาวตก

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน คือ $m'_i$ ($1 \le m'_i \le 100$) ซึ่งมีนิยามตามที่ระบุไว้ข้างต้น

อีก $n$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็มสี่จำนวน $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ ($-10^8 \le x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i} \le 10^8$, $0 \le |x_{1,i} - x_{2,i}|, |y_{1,i} - y_{2,i}| \le 5$) แทนตำแหน่งของแบบจำลองดาวตกดวงที่ $i$ ในภาพถ่ายทั้งสองภาพ

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบย่อย ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนจริง $n$ จำนวน ตามที่นิยามไว้ข้างต้น

สมมติว่าคำตอบของคุณคือ $x$ และคำตอบของกรรมการคือ $y$ คำตอบของคุณจะถือว่าถูกต้องก็ต่อเมื่อ $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$

ตัวอย่าง

ข้อมูลนำเข้า 1

2
2
1 2
0 0 1 0
1 1 0 1
3
1 2 3
1 0 0 -1
-1 0 0 1
0 1 1 0

ข้อมูลส่งออก 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

หมายเหตุ

สำหรับชุดทดสอบย่อยแรก แรงโน้มถ่วงสูงสุดระหว่างแบบจำลองดาวตก 1 และแบบจำลองดาวตก 2 เกิดขึ้นเมื่อพวกมันไปถึงตำแหน่ง $(0.5, 0)$ และ $(0.5, 1)$ ตามลำดับ ณ จุดนี้ คำตอบคือ $m'_1 m'_2 d_{\min}^2 = 2$