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:
// Code by ajcxsu
// Geometry template

#include<bits/stdc++.h>
#define EPS (1e-9)
using namespace std;

struct Point {
    double x,y;
    Point(double x=0,double y=0):x(x), y(y) {}

    Point operator +(Point p) { return Point(x+p.x,y+p.y); }
    Point operator -(Point p) { return Point(x-p.x,y-p.y); } // 加减
    Point operator *(double a) { return Point(x*a,y*a); }
    Point operator /(double a) { return Point(x/a,y/a); } // 数乘

    double norm() { return x*x+y*y; } // 范数
    double abs() { return sqrt(norm()); } // 大小

    bool operator < (const Point &p) { return x!=p.x?x<p.x:y<p.y; }
    bool operator == (const Point &p) { return fabs(p.x-x) < EPS && fabs(p.y-y) < EPS; }
} ;
typedef Point Vector;

double dot(const Point &a, const Point &b) {
    return a.x*b.x+a.y*b.y;
} // 内积
double cross(const Point &a, const Point &b) {
    return a.x*b.y-a.y*b.x;
} // 外积
bool equals(double a, double b) { return fabs(a-b)<EPS; } // 误差相等

struct Line {
    Point p1,p2;
} ;
typedef Line Seg;

/* 1 正交 2 平行 0 其他 */
int PO(Vector a, Vector b) {
    if(equals(dot(a,b), 0)) return 1;
    else if(equals(cross(a,b), 0)) return 2;
    else return 0;
}
int PO(Line a, Line b) { // 正交、平行判定
    return PO(a.p2-a.p1, b.p2-b.p1);
}

istream& operator >>(istream &in, Vector &a) {
    in>>a.x>>a.y;
    return in;
}
istream& operator >>(istream &in, Line &a) {
    in>>a.p1>>a.p2;
    return in;
} // 输入重载

Point project(Point a, Seg b) {
    Vector base=b.p2-b.p1;
    Vector hypo=a-b.p1;
    return b.p1+base*(dot(base, hypo)/ base.norm());
} // 投影

Point ref(Point a, Seg b) {
    Vector base=project(a,b)-a;
    return a+base*2;
} // 映像

int ccw(Vector a, Vector b) {
    if(cross(a,b)>EPS) return 1; // Counter clockwise
    else if(cross(a,b)<-EPS) return -1; // Clockwise
    else if(dot(a,b)<-EPS) return 2; // Online back
    else if(a.norm()<b.norm()) return -2; // Online front
    else return 0; // On segement
} // 判断顺时针逆时针
int ccw(Point p0, Point p1, Point p2) {
    return ccw(p1-p0, p2-p0);
}

bool intersect(Point p1, Point p2, Point p3, Point p4) {
    if( ccw(p1,p2,p3)*ccw(p1,p2,p4) <= 0 &&
        ccw(p3,p4,p1)*ccw(p3,p4,p2) <= 0) return 1;
    return 0;
}
bool intersect(Seg a, Seg b) {
    return intersect(a.p1, a.p2, b.p1, b.p2);
} // 判断线段是否相交

Point crossp(Seg a, Seg b) {
    Vector base=b.p2-b.p1, hypo=a.p1-b.p1, hypo2=a.p2-b.p1;
    double h1=fabs(cross(base,hypo))/base.abs();
    double h2=fabs(cross(base,hypo2))/base.abs();
    double t=h1/(h1+h2);
    return a.p1+(a.p2-a.p1)*t;
}


ostream& operator <<(ostream &out, Vector a) {
    out<<a.x<<' '<<a.y;
    return out;
} // 输出重载

int main() {
    cout.setf(ios::fixed);
    cout<<setprecision(10); // 设置输出精度

    int q;
    cin>>q;
    while(q--) {
        Seg a,b;
        cin>>a>>b;
        cout<<crossp(a,b)<<endl;
    }
    return 0;
}