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 JAVA):

Solution:
import java.util.*;
//import java.io.*;
import java.util.stream.IntStream;
public class Main{
    static int sum=0;
    public static void main (String args[]){
        //初期処理
        Scanner sc=new Scanner(System.in);
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // try{
            // int n = Integer.parseInt(br.readLine());
        int n = sc.nextInt();
        for(int i=0; i<n; i++){
            Vector p0 = new Vector(sc.nextInt(), sc.nextInt());
            Vector p1 = new Vector(sc.nextInt(), sc.nextInt());
            Vector p2 = new Vector(sc.nextInt(), sc.nextInt());
            Vector p3 = new Vector(sc.nextInt(), sc.nextInt());

            Vector ans = Vector.getCrossPoint(p0, p1, p2, p3);
            System.out.println(ans.x + " " + ans.y);
        }

    }
}

class Vector{
    public static final double EPS = 1e-10;
    public static final int COUNTER_CLOCKWISE=1;
    public static final int CLOCKWISE=-1;
    public static final int ONLINE_BACK=2;
    public static final int ONLINE_FRONT=-2;
    public static final int ON_SEGMENT=0;

    public double x,y;

    public Vector(){}
    public Vector(double x, double y){this.x=x;this.y=y;}

    public Vector plus(Vector p){return new Vector(this.x+p.x, this.y+p.y);}
    public Vector minus(Vector p){return new Vector(this.x-p.x, this.y-p.y);}
    public Vector multiple(double a){return new Vector(this.x*a, this.y*a);}
    public Vector divide(double a){return new Vector(this.x/a, this.y/a);}

    public double abs(){return Math.sqrt(this.norm());}
    public double norm(){return x*x+y*y;}

    
    public static double dot(Vector a, Vector b){
        return a.x*b.x+a.y*b.y;
    }

    public static double cross(Vector a, Vector b){
        return a.x*b.y-a.y*b.x;
    }

    //point.projectで垂線の足の座標
    public Vector project(Vector seg1, Vector seg2){
        Vector seg = seg2.minus(seg1);
        Vector relPoint = this.minus(seg1);
        double t = dot(seg, relPoint)/seg.norm();
        return seg1.plus(seg.multiple(t));
    }
    
    //point.reflectionで対称点
    public Vector reflection(Vector seg1, Vector seg2){
        Vector projected = this.project(seg1, seg2);
        Vector ashi = projected.minus(this);
        return this.plus(ashi.multiple(2));
    }

    //p0が始点
    public static int ccw(Vector p0, Vector p1, Vector p2){
        Vector s1 = p1.minus(p0);
        Vector s2 = p2.minus(p0);

        double cross = Vector.cross(s1, s2);
        double dot = Vector.dot(s1, s2);

        if(cross>0){return COUNTER_CLOCKWISE;}
        if(cross<0){return CLOCKWISE;}
        if(dot<0){return ONLINE_BACK;}
        if(s1.abs()<s2.abs()){return ONLINE_FRONT;}
        return ON_SEGMENT;
    }

    public static Boolean intersect(Vector p0, Vector p1, Vector p2, Vector p3){
        if(ccw(p0, p1, p2)*ccw(p0, p1, p3)<=0 && ccw(p2, p3, p0)*ccw(p2, p3, p1)<=0){
            return true;
        }else{
            return false;
        }
    }

    //平行四辺形から幾何的に
    public static Vector getCrossPoint(Vector p0, Vector p1, Vector p2, Vector p3){
        Vector base = p3.minus(p2);
        double d1 = Math.abs(cross(base, p0.minus(p2)));
        double d2 = Math.abs(cross(base, p1.minus(p2)));
        double t = d1/(d1+d2);
        return p0.plus((p1.minus(p0)).multiple(t));
    }
}