Problem: For given two segments s1 and s2, print the coordinate of the cross point of them.

s1 is formed by end points p0 and p1, and s2 is formed by end points p2 and p3.

Constraints

* 1 ≤ q ≤ 1000
* -10000 ≤ xpi, ypi ≤ 10000
* p0 ≠ p1 and p2 ≠ p3.
* The given segments have a cross point and are not in parallel.

Input

The entire input looks like:


q (the number of queries)
1st query
2nd query
...
qth query


Each query consists of integer coordinates of end points of s1 and s2 in the following format:


xp0 yp0 xp1 yp1 xp2 yp2 xp3 yp3


Output

For each query, print the coordinate of the cross point. The output values should be in a decimal fraction with an error less than 0.00000001.

Example

Input

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


Output

1.0000000000 0.0000000000
0.5000000000 0.5000000000
0.5000000000 0.5000000000

Solution (in CPP):

Solution:
#include <cmath>
#include <complex>
#include <algorithm>
#include <cassert>
using namespace std;

typedef long double Real;
typedef complex<Real> Point;
#define PCR Point const &
#define X real()
#define Y imag()

const Real EPS = 1e-10;
const Real INF = 1e100;
const Real PI = acos(-1);

struct Segment {
    Point p[2];
    Segment (PCR a = Point(), PCR b = Point()){
        p[0] = a, p[1] = b;
    }
    Point & operator [] (int k) { return p[k]; }
    Point const & operator [] (int k) const { return p[k]; }
};
typedef vector<Point> Polygon;
struct Circle { Real radius; Point center; };

Real dot(PCR a, PCR b){
    return a.X*b.X + a.Y*b.Y;
}
Real cross(PCR a, PCR b){
    return a.X*b.Y - a.Y*b.X;
}

Point pSP(Segment const & s, PCR p){
    Point base = s[1] - s[0];
    Real r = dot(p - s[0], base) / norm(base);
    return s[0] + base * r;
}

Point rSP(Segment const & s, PCR p){
    Point v = pSP(s,p) - p;
    return p + v * Real(2);
}

enum { LEFT = 1, RIGHT = -1, BACK = 2, FRONT = -2, ON = 0 };
// Includes end-points. Comment in to exclude.
int ccw(PCR x, PCR p, PCR q){
    Point a = p - x, b = q - x;
    if(cross(a,b) > EPS) return LEFT;
    if(cross(a,b) < -EPS) return RIGHT;
    if(/* abs(a) < EPS || */ dot(a,b) < -EPS) return BACK;
    if(/* abs(b) < EPS || */ norm(a) < norm(b)) return FRONT;
    return ON;
}

bool isParallel(Segment const & s, Segment const & t){
    return abs(cross(s[1]-s[0],t[1]-t[0])) < EPS;
}

bool isOrthogonal(Segment const & s, Segment const & t){
    return abs(dot(s[1]-s[0],t[1]-t[0])) < EPS;
}

// Includes end-points. Modify CCW to exclude
bool iSS(Segment const & s, Segment const & t){
    bool f1 = ccw(s[0],s[1],t[0]) * ccw(s[0],s[1],t[1]) <= 0;
    bool f2 = ccw(t[0],t[1],s[0]) * ccw(t[0],t[1],s[1]) <= 0;
    return f1 && f2;
}

Point cSS(Segment const & s, Segment const & t){
    assert(iSS(s,t));
    assert(!isParallel(s,t));
    Real d = cross(t[1]-t[0], s[1]-s[0]);
    return s[0] + (s[1] - s[0]) * cross(t[1]-t[0], t[1]-s[0]) * (1.0 / d);
}

#include <iostream>
#include <cstdio>

int main(){
    Segment s,t;
    Real x,y;
    int n; cin >> n;
    for(int i=0;i<n;i++){
        cin >> x >> y;
        s[0] = Point(x,y);
        cin >> x >> y;
        s[1] = Point(x,y);
        cin >> x >> y;
        t[0] = Point(x,y);
        cin >> x >> y;
        t[1] = Point(x,y);
        Point p = cSS(s,t);
        printf("%.10Lf %.10Lf\n", p.X,p.Y);
    }
}