交点

線分 s1, s2 について、それらの交点の座標を出力してください。

s1の端点を p0, p1、s2 の端点を p2, p3とします。

入力

１行目にクエリの数 q が与えられます。続く q 行に q 個のクエリが与えられます。 各クエリでは線分 s1、s2 の端点の座標が次の形式で与えられます。

xp0 yp0 xp1 yp1 xp2 yp2 xp3 yp3

入力はすべて整数で与えられます。

出力

各クエリについて、交点の座標(x, y)を１行に出力してください。出力は 0.00000001 以下の誤差を含んでもよいものとします。

制約

• 1 ≤ q ≤ 1,000
• −10,000 ≤ x_pi, y_pi ≤ 10,000
• p0, p1 は同一でない。
• p2, p3 は同一でない。
• s1, s2は一つの交点を持ち、平行でない。

入出力例

入力例

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

出力例

1.0000000000 0.0000000000
0.5000000000 0.5000000000
0.5000000000 0.5000000000

Note

      解説      

---