3407. Ardenia

Welcome to Ardenia. Ardenia is a mythical land, filled with adventure and danger, dwarves and dragons, mages and rouges. And puzzles. Lots of puzzles. Actually, the love for puzzles is the most important life ingredient of the inhabitants, and the only part they have in common.

This month, the people of Ardenia wonder what is the distance between two line segments in three dimensional space. (The distance between segments is defined as the minimum among distances between two points of different segments.) Actually, this problem had originally some motivation, but as nobody from Ardenia cares about motivations, neither should you.

输入格式

The input contains several test cases. The first line of the input contains a positive integer $Z \le 10^5$, denoting the number of test cases. Then $Z$ test cases follow.

For each test case, the first line of the input instance contains six space-separated integers $x_1, y_1, z_1, x_2, y_2, z_2 \in [−20, 20]$.

Points $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$ are the (different) endpoints of the first segment. The second line contains six integers in the same format, describing the second segment.

输出格式

You should output a single line, for each test case, consisting of two co-prime integers $l$ and $m > 0$, such that $l/m$ is the squared distance between the given two segments.

样例

Input
2
0 0 0 1 1 1
1 1 1 2 2 2
1 0 0 0 1 0
1 1 0 2 2 0

Output
0 1
1 2


1 人解决，1 人已尝试。

1 份提交通过，共有 3 份提交。

9.3 EMB 奖励。