Polyline

You are given $N$ segments placed in a plane. You may move them anywhere in the plane, but you cannot rotate or reflect them. Your task is to connect the segment ends to form a single open polyline and determine the maximum possible distance between the endpoints of this polyline.

Each segment is given by a pair $(X_{i}, Y_{i})$ , representing the segment from $(0, 0)$ to $(X_{i}, Y_{i})$ .

An open polyline is an arrangement of segments in a sequence such that the start of each segment is placed exactly at the end of the previous segment. The first and last segments each have one free endpoint — these two free endpoints are the ends of the polyline.

You need to arrange the given $N$ segments to maximize the distance between these two free endpoints.

Constraints

$1 \leq N \leq 100$
$- 1000 \leq X_{i}, Y_{i} \leq 1000$
$X_{i}$ and $Y_{i}$ are integers
No $(X_{i}, Y_{i})$ will be $(0, 0)$

Input Format

The first line contains an integer $T$ — the number of test cases.
Each test case is described as follows:
The first line contains an integer $N$ — the number of segments.
The next $N$ lines each contain two integers $X_{i}$ and $Y_{i}$ .

Output Format

For each test case $t$ ( $1 \leq t \leq T$ ), output Case #t: d, where $d$ is the maximum possible distance between the endpoints of the polyline, with a relative or absolute error of at most $1 0^{- 6}$ .

Example

Input

Output

Case #1: 13.4164078650
Case #2: 11.0000000000

Explanation

For the first sample, see the pictures below for the original placement of the given segments, and the optimal configuration that results in the maximum possible distance between the ends of the corresponding polyline.

sample