Ardenia

Time limit1sMemory limit128 MB

Summary

Given two 3D segments per test case (up to 1e5), compute the exact squared minimum distance between them as a reduced fraction.

Level: Hard8 of 10
Topics: Geometry, Math, Number theory
Solved: No attempts yet

Problem

Welcome to Ardenia. Ardenia is a mythical land, filled with adventure and danger, dwarves and dragons, mages and rogues. And puzzles. Lots of puzzles. In fact, the love for puzzles is the most important ingredient of life for its inhabitants, and the only thing they all have in common.

This month, the people of Ardenia wonder what the distance is between two line segments in three-dimensional space. (The distance between two segments is defined as the minimum, over all choices of a point on one segment and a point on the other, of the distance between those two points.) This problem originally had some motivation, but since nobody in Ardenia cares about motivations, neither should you.

The input contains several test cases. The first line contains a positive integer Z (Z ≤ 10^5), the number of test cases. Then Z test cases follow, each in the format described under Input. For each test case, print one line in the format described under Output.

Input

The first line of a test case contains six space-separated integers x1, y1, z1, x2, y2, z2, each between −20 and 20. The points (x1, y1, z1) and (x2, y2, z2) are the two (distinct) endpoints of the first segment. The second line contains six integers in the same format, describing the second segment.

Output

For each test case, print a single line with two coprime integers ℓ and m (m > 0) separated by a space, such that ℓ/m equals the squared distance between the two given segments. The squared distance is always rational, so it can be written as a reduced fraction ℓ/m; if the distance is 0, print 0 1.

Examples7

Example 1

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

Expected output

0 1
1 2

Example 2
Input
```
1
-1 0 0 1 0 0
0 -1 1 0 1 1
```
Expected output
```
1 1
```
Example 3
Input
```
1
-1 -1 0 1 1 0
-1 1 0 1 -1 0
```
Expected output
```
0 1
```
Example 4
Input
```
1
0 0 0 1 0 0
3 0 0 5 0 0
```
Expected output
```
4 1
```
Example 5
Input
```
1
0 0 0 4 0 0
2 0 0 2 3 0
```
Expected output
```
0 1
```
Example 6
Input
```
1
0 0 0 2 0 0
0 3 4 2 3 4
```
Expected output
```
25 1
```
Example 7
Input
```
1
0 0 0 2 1 0
1 0 1 1 3 2
```
Expected output
```
49 41
```