Under construction

Still being built. Things may change

Temple of Dune

Time limit1sMemory limit128 MB

Summary
Given three points that are vertices of some regular polygon, find the minimum possible number of vertices.
Level

Hard8 of 10

Topics
Geometry, Math, Number theory
Solved
No attempts yet

Problem

The Archaeologists of the Current Millennium (ACM) now and then discover ancient artifacts located at the vertices of regular polygons. Uncovering each artifact requires moving the single sand dune that covers it. One day the archaeologists uncover three artifacts sitting at three distinct vertices of a regular polygon.

Given these three points as distinct vertices of some regular polygon, determine the fewest number of vertices such a polygon could have. In other words, output the smallest number of vertices among all regular polygons that have the three given points as vertices.

Input

The first line contains a positive integer, the number of test cases. Each test case is a single line of six real numbers giving the x and y coordinates of three distinct vertices of a regular polygon, in the order x1 y1 x2 y2 x3 y3.

Output

For each test case, output on its own line a single integer: the fewest number of vertices a regular polygon having the three given points as vertices could have.

You may assume that every test case gives three distinct vertices of a regular polygon with at most 200 vertices.

Examples3

  1. Example 1

    Input
    4
10.00000 0.00000 0.00000 -10.00000 -10.00000 0.00000
22.23086 0.42320 -4.87328 11.92822 1.76914 27.57680
156.71567 -13.63236 139.03195 -22.04236 137.96925 -11.70517
129.400249 -44.695226 122.278798 -53.696996 44.828427 -83.507917
    Expected output
    4
6
23
100

  2. Example 2

    Input
    1
49.750208 4.991671 -29.198018 40.589109 -20.552190 -45.580780
    Expected output
    3

  3. Example 3

    Input
    1
68.604660 13.906853 -13.906853 68.604660 -68.604660 -13.906853
    Expected output
    4