Equivalent Deformation

Given two equal-area triangles, find the minimum number of vertex-sliding operations that map the first exactly onto the second.

Hard9GeometryImplementationGreedyBrute forceNo attempts yetTime limit2sMemory limit512 MB

Problem

Two triangles T1T_1 and T2T_2 of the same area lie on a plane. Apply the operation below to T1T_1 several times so that T1T_1 is exactly superposed on T2T_2. A vertex of T1T_1 may land on any vertex of T2T_2. Compute the minimum number of operations needed to superpose T1T_1 on T2T_2.

Operation: choose one vertex of the triangle and move it to an arbitrary point on the line that passes through the vertex and runs parallel to the opposite side.

An operation example

An operation example

The figure below shows one possible sequence of operations for the first dataset of the sample input.

A sequence of operations

Input

The input consists of at most 2000 datasets, each in the following format.

x11 y11
x12 y12
x13 y13
x21 y21
x22 y22
x23 y23

xijx_{ij} and yijy_{ij} are the xx and yy coordinate of the jj-th vertex of TiT_i.

Each dataset satisfies the following conditions.

  • Every coordinate is an integer with absolute value at most 1000.
  • T1T_1 and T2T_2 have the same area, and that area is positive.
  • The six given vertices are all distinct points.

An empty line is placed between datasets. The input ends at end of file.

Output

For each dataset, output the minimum number of operations in one line. If five or more operations are required, output Many instead of the count.

A vertex may have non-integral coordinates after it is moved.

For any input satisfying the conditions above, the required number of operations can be proven to be bounded by some constant.