Problem: Scientist Frank, majoring in electrochemistry, has developed line-shaped strange electrodes called F-electrodes. During being activated, each F-electrode causes a special potential on and between the two lines touching the F-electrode’s endpoints at a right angle. Then electrically-charged particles located inside the potential area get to move in the direction parallel to the potential boundary (i.e. perpendicular to the F-electrode), either toward or against F-electrode. The moving direction can be easily controlled between the two possibles; it is also possible to get particles to pass through F-electrodes. In addition, unlike ordinary electrodes, F-electrodes can affect particles even infinitely far away, as long as those particles are located inside the potential area. On the other hand, two different F-electrodes cannot be activated at a time, since their potentials conflict strongly.

We can move particles on our will by controlling F-electrodes. However, in some cases, we cannot lead them to the desired positions due to the potential areas being limited. To evaluate usefulness of F-electrodes from some aspect, Frank has asked you the following task: to write a program that finds the shortest distances from the particles’ initial positions to their destinations with the given sets of F-electrodes.

<image>



Input

The input consists of multiple test cases. The first line of each case contains N (1 ≤ N ≤ 100) which represents the number of F-electrodes. The second line contains four integers xs, ys, xt and yt, where (xs, ys) and (xt, yt) indicate the particle’s initial position and destination. Then the description of N F-electrodes follow. Each line contains four integers Fxs, Fys, Fxt and Fyt, where (Fxs, Fys) and (Fxt, Fyt ) indicate the two endpoints of an F-electrode. All coordinate values range from 0 to 100 inclusive.

The input is terminated by a case with N = 0.

Output

Your program must output the case number followed by the shortest distance between the initial position to the destination. Output “Impossible” (without quotes) as the distance if it is impossible to lead the elementary particle to the destination. Your answers must be printed with five digits after the decimal point. No absolute error in your answers may exceed 10-5.

Example

Input

2
2 1 2 2
0 0 1 0
0 1 0 2
0


Output

Case 1: 3.00000

Solution (in CPP):

Solution:
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

const int N = 300 + 10;
const int V = N * N;
const int M = V * 10;
const double INF = 1e10;
const double EPS = 1e-8;

int sign(long double x)
{
	return x < -EPS ? -1 : x > EPS;
}

struct Edge
{
	double w;
	int t;
	Edge *n;
};

Edge edges[M], *totEdge, *firstEdge[V];

struct Point
{
	long double x, y;
	Point() {}
	Point(long double x, long double y) : x(x), y(y) {
	}
	Point operator + (const Point &that) const {
		return Point(x + that.x, y + that.y);
	}
	Point operator - (const Point &that) const {
		return Point(x - that.x, y - that.y);
	}
	Point operator * (const long double &that) const {
		return Point(x * that, y * that);
	}
	Point operator / (const long double &that) const {
		return Point(x / that, y / that);
	}
	void read() {
		cin >> x >> y;
	}
	Point rot90() {
		return Point(y, -x);
	}
	int operator < (const Point &that) const {
		int d = sign(x - that.x);
		if (d) return d < 0;
		return sign(y - that.y) < 0;
	}
	long double det(const Point &that) const {
		return x * that.y - that.x * y;
	}
	long double distTo(const Point &that) const {
		return hypot(x - that.x, y - that.y);
	}
	void write() {
		cout << "(" << x << "," << y << ") ";
	}
};

#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

int n, tot;
vector<pair<Point, Point> > lines;
vector<Point> pointList;
vector<int> pointOnLine[N];
map<Point, int> points;
Point s, t;
Point a[N][2];

int insert(Point u)
{
	if (points.count(u) == 0) {
		pointList.push_back(u);
		points[u] = tot ++;
	}
	return points[u];
}

Point isSS(Point p1, Point p2, Point q1, Point q2)
{
	long double a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
	return (p1 * a2 + p2 * a1) / (a1 + a2);
}

int cmp(const int &a, const int &b)
{
	return pointList[a] < pointList[b];
}

void addEdge(int s, int t, long double w)
{
	Edge *e = totEdge ++;
	e->w = w; e->t = t; e->n = firstEdge[s]; firstEdge[s] = e;
}

long double dij(int s, int t)
{
	priority_queue< pair<double, int> > que;
	int in[V];
	double dis[V];
	for(int i = 0; i < tot; ++ i) {
		dis[i] = INF;
		in[i] = false;
	}
	dis[s] = 0;
	que.push(make_pair(0, s));

	for( ; que.size(); ) {
		int u = que.top().second;
		que.pop();
		if (in[u]) continue;
		in[u] = true;
		if (u == t) return dis[t];
		for(Edge *e = firstEdge[u]; e; e = e->n) {
			int v = e->t;
			if (dis[v] > dis[u] + e->w) {
				dis[v] = dis[u] + e->w;
				que.push(make_pair(-dis[v], v));
			}
		}
	}
	return INF;
}

void solve()
{
	lines.clear();
	s.read(); t.read();
	for(int i = 0; i < n; ++ i) {
		a[i][0].read();
		a[i][1].read();
		Point vec = (a[i][1] - a[i][0]).rot90();
		Point s1 = a[i][0], t1 = s1 + vec;
		Point s2 = a[i][1], t2 = s2 + vec;
		lines.push_back(make_pair(s1, t1));
		lines.push_back(make_pair(s2, t2));
		if (crossOp(s1, t1, s) * crossOp(s2, t2, s) <= 0) {
			lines.push_back(make_pair(s, s + vec));
		}
		if (crossOp(s1, t1, t) * crossOp(s2, t2, t) <= 0) {
			lines.push_back(make_pair(t, t + vec));
		}
	}
	
	pointList.clear();
	tot = 0;
	points.clear();
	insert(s);
	insert(t);

	for(int i = 0; i < lines.size(); ++ i) {
		pointOnLine[i].clear();
	}
	for(int i = 0; i < lines.size(); ++ i) {
		if (crossOp(lines[i].first, lines[i].second, s) == 0) {
			pointOnLine[i].push_back(insert(s));
		}
		if (crossOp(lines[i].first, lines[i].second, t) == 0) {
			pointOnLine[i].push_back(insert(t));
		}
		for(int j = i + 1; j < lines.size(); ++ j) {
			if (sign((lines[i].second - lines[i].first).det(lines[j].second - lines[j].first)) == 0) 
				continue;
			Point p = isSS(lines[i].first, lines[i].second, lines[j].first, lines[j].second);
			int id = insert(p);
			pointOnLine[i].push_back(id);
			pointOnLine[j].push_back(id);
		}
	}

	totEdge = edges;
	for(int i = 0; i < tot; ++ i) {
		firstEdge[i] = 0;
	}
	for(int i = 0; i < lines.size(); ++ i) {
		sort(pointOnLine[i].begin(), pointOnLine[i].end(), cmp);
		pointOnLine[i].resize(unique(pointOnLine[i].begin(), pointOnLine[i].end()) - pointOnLine[i].begin());
		for(int j = 1; j < pointOnLine[i].size(); ++ j) {
			int u = pointOnLine[i][j - 1], v = pointOnLine[i][j];
			addEdge(u, v, pointList[u].distTo(pointList[v]));
			addEdge(v, u, pointList[u].distTo(pointList[v]));
		}
	}

	double ret = dij(points[s], points[t]);
	if (ret >= INF) cout << "Impossible" << endl;
	else {
		printf("%.12f\n", (double)ret);
	}
}

int main()
{
	int test = 0;
	for( ; cin >> n && n; ) {
		printf("Case %d: ", ++ test);
		solve();
	}
	return 0;
}