#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-10;
bool dcmp(double d, double d2 = 0) { return abs(d - d2) < eps; }

struct vec {
  double x, y;
  vec(double x, double y) : x(x), y(y) {}
  vec() : x(0), y(0) {}
  const bool operator==(const vec &v) const {
    return dcmp(x, v.x) && dcmp(y, v.y);
  }
  const bool operator!=(const vec &v) const { return !(*this == v); }
  const vec operator+(const vec &v) const { return vec(x + v.x, y + v.y); }
  const vec operator-() const { return vec(-x, -y); }
  const vec operator-(const vec &v) const { return *this + (-v); }
  const vec operator*(const double d) const { return vec(x * d, y * d); }
  const vec operator/(const double d) const { return *this * (1 / d); }
  const vec unit() const { return *this / len(); };
  const double len() const { return sqrt(x * x + y * y); }
  const double dot(const vec &v) const { return x * v.x + y * v.y; }
  const double cross(const vec &v) const { return x * v.y - y * v.x; }
  const bool parallel(const vec &v) const { return dcmp(cross(v)); }
  const bool perpendicular(const vec &v) const { return dcmp(dot(v)); }
};

typedef vec point;

template <class T> struct optional {
  bool has;
  T val;
  optional() : has(false) {}
  optional(T t) : has(true), val(t) {}
};

struct line {
  double a, b, c;
  line(point p1, point p2) {
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = p1.x * p2.y - p2.x * p1.y;
  }
  optional<point> intersect(line l) {
    if (dcmp(a * l.b, b * l.a))
      return optional<point>();
    return point((c * l.b - b * l.c) / (a * l.b - b * l.a),
                 -(c * l.a - a * l.c) / (a * l.b - b * l.a));
  }
};

struct segment {
  point p1, p2;
  point intersect(segment s) {}
};

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    point p0, p1, p2, p3;
    cin >> p0.x >> p0.y >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;
    line l0(p0, p1);
    line l1(p2, p3);
    point p = l0.intersect(l1).val;
    printf("%.9lf %.9lf\n", p.x, p.y);
  }
}

### Prompt

In cpp, your task is to solve the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-10;
bool dcmp(double d, double d2 = 0) { return abs(d - d2) < eps; }

struct vec {
  double x, y;
  vec(double x, double y) : x(x), y(y) {}
  vec() : x(0), y(0) {}
  const bool operator==(const vec &v) const {
    return dcmp(x, v.x) && dcmp(y, v.y);
  }
  const bool operator!=(const vec &v) const { return !(*this == v); }
  const vec operator+(const vec &v) const { return vec(x + v.x, y + v.y); }
  const vec operator-() const { return vec(-x, -y); }
  const vec operator-(const vec &v) const { return *this + (-v); }
  const vec operator*(const double d) const { return vec(x * d, y * d); }
  const vec operator/(const double d) const { return *this * (1 / d); }
  const vec unit() const { return *this / len(); };
  const double len() const { return sqrt(x * x + y * y); }
  const double dot(const vec &v) const { return x * v.x + y * v.y; }
  const double cross(const vec &v) const { return x * v.y - y * v.x; }
  const bool parallel(const vec &v) const { return dcmp(cross(v)); }
  const bool perpendicular(const vec &v) const { return dcmp(dot(v)); }
};

typedef vec point;

template <class T> struct optional {
  bool has;
  T val;
  optional() : has(false) {}
  optional(T t) : has(true), val(t) {}
};

struct line {
  double a, b, c;
  line(point p1, point p2) {
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = p1.x * p2.y - p2.x * p1.y;
  }
  optional<point> intersect(line l) {
    if (dcmp(a * l.b, b * l.a))
      return optional<point>();
    return point((c * l.b - b * l.c) / (a * l.b - b * l.a),
                 -(c * l.a - a * l.c) / (a * l.b - b * l.a));
  }
};

struct segment {
  point p1, p2;
  point intersect(segment s) {}
};

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    point p0, p1, p2, p3;
    cin >> p0.x >> p0.y >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;
    line l0(p0, p1);
    line l1(p2, p3);
    point p = l0.intersect(l1).val;
    printf("%.9lf %.9lf\n", p.x, p.y);
  }
}

```