This is an answer-submission problem.

Background

In the Deterrence Era, year 2233, humanity mastered a new technology: based on the principles of quantum mechanics, cosmic broadcasts from the Earth's surface can transmit signals at superluminal speeds to a plane tangent to the Earth at the point of the broadcast's coordinates.

Since the Gravity broadcasted its coordinates, it has carried the seeds of human civilization, flying deep into the universe, far away from the solar system.

In the DX3906 Galaxy, Black Domain Era, year 3333, the Gravity discovered a massive X-galaxy, several light-years in diameter, containing three planets suitable for human habitation, distributed in different corners of the X-galaxy. After discussions, some members of the Gravity chose to settle on these three planets.

For the settled humans, real-time communication is essential, so the set of devices invented 1,100 years ago came in handy. Clearly, the three planets can communicate with each other if and only if the working tangent planes of the three cosmic broadcasts coincide perfectly.

Now, the planetary chief, Amoeba, has found you, a skilled programmer, and hopes you can calculate all possible schemes for establishing cosmic broadcasts.

After you accepted this task, you said to yourself, "What's this? I, ygg, can handle this in minutes." However, Amoeba, who is good at reading minds, immediately called you back and earnestly told you that human civilization must continue, so you should solve the station-building scheme for $K$ planets in $K$-dimensional space. The chief didn't make it too difficult for you; you only need to solve for $K \le 10$, because the universe, when adding the time dimension, is 11-dimensional.

When you finished writing the program in 3 minutes, Amoeba looked at it and gave you a dual-vector foil — because you didn't account for that case in your program.

Description

Given the coordinate dimension $K \ge 2$, and $K$ spheres in $K$-dimensional coordinates (which can degenerate into points, i.e., the radius can be zero), find all common tangent planes of these $K$ spheres.

The data guarantees that there will be no cases with no solutions or infinitely many solutions, but it does not guarantee that all spheres are disjoint.

Here are some definitions:

• Distance: In $K$-dimensional space, given two points $A(a_0,a_1,\cdots,a_{K-1})$ and $B(b_0,b_1,\cdots,b_{K-1})$, the distance between $AB$ is $$\displaystyle |AB|=\sqrt{\sum_{i=0}^{K-1} (a_i-b_i)^2}$$
• Sphere: In $K$-dimensional space, the set of points at a constant distance $r$ from a fixed point $A$. Point $A$ is called the center, and $r$ is the radius of the sphere.
  • When $K=2$, this is the circle familiar from high school.
• Hyperplane: The set of points equidistant from two points $A$ and $B$ in $K$-dimensional space. In $K$-dimensional space, the dimension of a hyperplane is $K-1$.
  • When $K=2$, this is the straight line (perpendicular bisector) familiar from high school.
• Tangent plane of a sphere: A hyperplane $P$ that has exactly one intersection point with sphere $A$.
• Common tangent plane of spheres: A hyperplane $P$ that is a tangent plane to all spheres.

Input

This is an answer-submission problem with 8 input files, named 1.in ~ 8.in.

Each test case contains multiple data sets. For each test case:

• First line: The number of data sets $T$, where $T \le 10$.
• For each data set:
  • First line: The coordinate dimension $K$, where $K \le 10$.
  • Next $K$ lines: Each line contains $K+1$ real numbers. The first $K$ numbers of the $i$-th line represent the coordinates of the center of the $i$-th sphere, and the $(K+1)$-th number represents the radius of the $i$-th sphere.

Output

For each input file, you need to submit the corresponding output file 1.out ~ 8.out.

For each data set in each test case:

• First line: A positive integer $S$, representing the total number of tangent plane solutions you found in this data set. If no solutions are found, you must output 0; otherwise, it will affect the scoring of subsequent data, and the consequences will be borne by the contestant.
• Next $S \times K$ lines: Each line contains $K$ decimal numbers. For the corresponding $S(i-1)+j$-th line, it represents the coordinates of the tangent point on the $j$-th sphere for the $i$-th solution.
• Last line: Output an empty line.

You may add any content at the end of the output file; this will not affect your score. We suggest you write some meaningful content here (such as a brief method) so that we can perform statistical analysis after the exam. The size of a single output file must not exceed 4M.

Examples

Input 1

(input data)

Output 1

(output data)

Note

Following the order in Example 0, the visualization results are as follows:

For the 4th data set, due to space limitations, the 8 schemes cannot be presented here one by one.

For the 5th data set, it cannot be visualized due to the current level of human technology.

We sincerely apologize for this.

Scoring

• There is no requirement for the order of the solutions. For a solution, let the output answer be $(A_0, A_1, \cdots, A_{K-1})$. If there exists a standard answer $(B_0, B_1, \cdots, B_{K-1})$ such that $\displaystyle\sum_{i=0}^{K-1} |A_iB_i|^2 \le 10^{-12}$, then this output answer will be judged as correct.
• In the same data set of each test case, we will count the number of common tangent planes that match the standard answers. Each standard answer will be matched at most once. Outputting duplicate common tangent planes will not result in a penalty. The correct ratio for the $i$-th data set is the number of matched standard answers divided by the total number of standard answers, denoted as $rate_i$.
• Scoring method for each test case:
  1. If your output format is invalid, or the parameters do not meet the problem requirements, or the number of answers in a set exceeds twice the number of standard answers for that set (excluding twice), you will receive 0 points.
  2. Without violating the above conditions, if you correctly answer any solution for any data set, you will receive at least one point; you must answer all solutions correctly to receive the full score for that test case.
  3. Without violating the above conditions, let $T$ be the total number of data sets, $rate_i$ be the correct ratio for the $i$-th data set, and $score$ be the total points for the test case. Then: $$Yourscore = \frac{score}{T} \cdot \sum_{i=1}^T \sqrt{rate_i}$$ The result is rounded to the nearest integer, such that $Yourscore \in [1, score-1]$.

Subtasks

The points for each test case are as follows: