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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.CountDownLatch;

import javax.sound.midi.MidiMessage;
 
public class Main {
		static long MOD=(long) (Math.pow(10, 9)+7);
		static boolean[] visited;
	public static void main(String[] args){
		PrintWriter out = new PrintWriter(System.out);
		InputReader sc=new InputReader(System.in);
		int N=sc.nextInt();
		Geometric geometric=new Geometric();
		for (int i = 0; i < N; i++) {
			double x0 = sc.nextDouble();
			double y0 = sc.nextDouble();
			double x1 = sc.nextDouble();
			double y1 = sc.nextDouble();
			double x2 = sc.nextDouble();
			double y2 = sc.nextDouble();
			double x3 = sc.nextDouble();
			double y3 = sc.nextDouble();
			String[] ans=geometric.getCrossPoint(x0, y0, x1, y1, x2, y2, x3, y3);
			out.println(ans[0]+" "+ans[1]);
		}
		out.flush();
	}
	static class Geometric{
		static final double eps = 0.0000000001;
		double[] project(double x1, double y1, double x2, double y2, double px, double py){
			//(x1,y1)と(x2,y2)を直線lとして、(px,py)からlに下した垂線の足をもとめる。
	        if(y1 == y2) {
	        	double[] ans= {px,y1};
	        	return ans;
	        	}
	        else if(x1 == x2) {
	        	double[] ans= {x1,py};
	        	return ans;
	        }
	        else{
	            double katamuki1 = (y2 - y1)/(x2 - x1);
	            double seppen1 = -katamuki1 * x1 + y1;
	            double katamuki2 = -1.0 / katamuki1;
	            double seppen2 = -katamuki2 * px + py;
	            double ansx = (seppen2 - seppen1)/(katamuki1 - katamuki2);
	            double ansy = ansx * katamuki1 + seppen1;
	            double[] ans= {ansx,ansy};
	            return ans;
	        }
	    }
	    double[] project2(double x1, double y1, double x2, double y2, double px, double py){
	    	//(x1,y1)と(x2,y2)を直線lとして、lに対して(px,py)の対称な点をもとめる。
	        if(y1 == y2) {
	        	double[] ans= {px,(py - 2*(py - y1))};
	        	return ans;
	        }
	        else if(x1 == x2) {
	        	double[] ans= {(px - 2*(px - x1)),py};
	        	return ans;
	        }
	        else{
	            double katamuki1 = (y2 - y1)/(x2 - x1);
	            double seppen1 = -1.0 * katamuki1 * x1 + y1;
	            double katamuki2 = -1.0 / katamuki1;
	            double seppen2 = -1.0 * katamuki2 * px + py;
	            double ansx = (seppen2 - seppen1)/(katamuki1 - katamuki2);
	            double ansy = ansx * katamuki1 + seppen1;
	            double[] ans= {(px - 2*(px - ansx)),(py- 2 * (py - ansy))};
	            return ans;
	        }
	    }
	    public double d2(double x0,double y0,double x1,double y1){
			return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);
		}
		public double d1(double x0,double y0,double x1,double y1){
			return Math.sqrt((x0-x1)*(x0-x1) + (y0-y1)*(y0-y1));
		}
		boolean iscrosssegmentline(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3) {
			//	交差するなら１しないなら0を返す。
			double s=0;
			double t=0;
			double s_=0;
			double t_=0;
		    s = (x0 - x1) * (y2 - y0) - (y0 - y1) * (x2 - x0);
		    t = (x0 - x1) * (y3 - y0) - (y0 - y1) * (x3 - x0);
		    if (s * t > 0) return false;
		    s_ = (x2 - x3) * (y0 - y2) - (y2 - y3) * (x0 - x2);
		    t_ = (x2 - x3) * (y1 - y2) - (y2 - y3) * (x1 - x2);
		    if (s_ * t_ > 0) return false;
		    if (s*t==0&&s_*t_==0) {
				if (this.direction(x0, y0, x1, y1, x2, y2)==5||this.direction(x0, y0, x1, y1, x3, y3)==5) {
					return true;
				}
				else if (this.direction(x2, y2, x3, y3, x0, y0)==5||this.direction(x2, y2, x3, y3, x1, y1)==5) {
					return true;
				}
				else {
					return false;
				}
			}
		    return true;
		}
	    int direction(double x0,double y0,double x1,double y1,double x2,double y2){
			//x0 y0を起点としてp1ベクトル（x1-x0,y1-y0）から見てp2ベクトルが、反時計回りなら１、時計回りなら２、反対方向なら３、
	    	//同じ方向かつp2のほうが大きい場合４、以下の場合５．
			if(x1 == x0 && y1 == y0){
				return 4;
			}
			else if(x2 == x0 && y2 == y0){
				return 5;
			}
			
			//外積の第三成分 = |→p1||→p2|sinθ
			double det = (x1 -x0)*(y2-y0) - (x2 -x0)*(y1 - y0);
			
			if(det>eps){
				return 1;
			}
			else if(det<-eps){
				return 2;
			}
			else{	//同一直線状
				if((x1-x0 >0 == x2-x0 <0) && x1-x0 != 0){	//反対側
					return 3;
				}
				else if((y1-y0 >0 == y2-y0 <0) && y1-y0 != 0){	//反対側
					return 3;
				}
				else{
					double d10 = d2(x0,y0,x1,y1);	//p1とp0の距離^2
					double d20 = d2(x0,y0,x2,y2);	//p2とp0の距離^2
					if(d10 < d20){	//p2のほうが遠い
						return 4;
					}
					else{
						return 5;
					}
				}
			}
		}
	    String[] getCrossPoint(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3) {
			double x;
			double y;
			if(x1 == x0) {
				x = x0;
				y = ((y3 - y2) / (x3 - x2)) * x + (y2 - ((y3 - y2) / (x3 - x2)) * x2);
			} else if(x3 == x2) {
				x = x2;
				y = ((y1 - y0) / (x1 - x0)) * x + (y0 - ((y1 - y0) / (x1 - x0)) * x0);
			} else {
				x = ((y0 - ((y1 - y0) / (x1 - x0)) * x0) - (y2 - ((y3 - y2) / (x3 - x2)) * x2))/(((y3 - y2) / (x3 - x2)) - ((y1 - y0) / (x1 - x0)));
				y = ((y1 - y0) / (x1 - x0)) * x + (y0 - ((y1 - y0) / (x1 - x0)) * x0);
			}
			DecimalFormat df = new DecimalFormat("0.00000000");
			String[] ans= {df.format(x),df.format(y)};
			return ans;
	    }
	    int paralell_or_vertical(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3) {
	    	//平行なら2　垂直なら1　それ以外は０を返す。
	    	double naiseki=(x1-x0)*(x3-x2)+(y1-y0)*(y3-y2);
	    	double d1=Math.sqrt(d2(x0, y0, x1, y1));
	    	double d2=Math.sqrt(d2(x2, y2, x3, y3));
	    	double cos=naiseki/(d1*d2);
	    	
	    	if (cos+eps>=1||cos-eps<=-1) {
				return 2;
			}
	    	else if(cos<eps&&cos>-eps){
				return 1;
			}
	    	else {
				return 0;
			}
	    }
	}
	static class InputReader { 
		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;
		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}
 
		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}
 
		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}
 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
 
		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}
 
		public boolean hasNext() {
			skip();
			return hasNextByte();
		}
 
		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
 
		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public double nextDouble() {
			return Double.parseDouble(next());
		}
 
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
 
		public char[][] nextCharMap(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++)
				map[i] = next().toCharArray();
			return map;
		}
	}
}