# 3472. Center

There are $n$ weighted points in a plane. Point $i$ is at $(x_i, y_i)$ and has weight $w_i$.

In this problem, we need to find a special center of these points. The center is a point $(X, Y)$ such that $\sum_{i=1}^n \max(|X-x_i|, |Y-y_i|) \cdot w_i$ is minimum.

### 输入格式

The input starts with one line containing exactly one integer $T$, which is the number of test cases. $T$ test cases follow.

Each test case begins with one line containing one integer $n$. $n$ lines follow. Each line contains three space-separated real numbers $x_i$, $y_i$, and $w_i$. $x_i$, $y_i$ and $w_i$ have exactly $2$ digits after the decimal point.

Limits:

• $1 \le T \le 10$.
• $-1000.00 \le x_i \le 1000.00$.
• $-1000.00 \le y_i \le 1000.00$.
• $1 \le n \le 10000$.
• $1.0 \le w_i \le 1000.0$.

### 输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the answer.

y will be considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer.

### 样例

Input
3
2
0.00 0.00 1.00
1.00 0.00 1.00
4
1.00 1.00 1.00
1.00 -1.00 1.00
-1.00 1.00 1.00
-1.00 -1.00 1.00
2
0.00 0.00 1.00
1.00 0.00 2.00

Output
Case #1: 1.0
Case #2: 4.0
Case #3: 1.0


2 人解决，2 人已尝试。

4 份提交通过，共有 6 份提交。

8.0 EMB 奖励。