時間制限 : sec, メモリ制限 : KB
English / Japanese  

交点

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

s1の端点を p0, p1s2 の端点を p2, p3とします。

入力

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

xp0 yp0 xp1 yp1 xp2 yp2 xp3 yp3

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

出力

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

制約

  • 1 ≤ q ≤ 1,000
  • −10,000 ≤ xpi, ypi ≤ 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

      解説