High School Programming League Problems Archive

You are given four points in a plane. Find out which type of a quadrilateral is determined by these 4 points. 

If several types of quadrilaterals are possible, provide only one name, chosen according to the following list of priorities:

1. Square
2. Rectangle
3. Rhombus
4. Rhomboid
5. Kite
6. Trapezoid
7. Convex      - Convex quadrilateral which cannot be classified as one of those listed above.
8. Dart          - Concave two pairs with equal neighboring sides (like a kite but concave)
9. Concave    - Concave quadrilateral which cannot be classified as a dart.
10. None         - Three or more points are collinear or two or more points are the same.

Input

The first line contains an integer T, the number of test cases (T <= 10000).

In the next T lines there are eight integers in each line: Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. All coordinates are between -10^9 and 10^9, inclusive. For quadrilaterals which match any of the types 1 to 9, the points of quadrilaterals will be ordered anticlockwise.

Output

For every test, write which kind of quadrilateral is determined by these four points.

Example

Input:
10
0 0 1 1 2 2 0 2 
0 0 1 -1 2 0 1 1
0 0 1 -2 2 0 1 2
0 0 1 -1 2 0 1 2
0 0 1 1 2 0 1 2 
2 0 3 2 0 3 0 0
0 0 1 1 3 0 1 2
3 2 0 2 0 0 3 0
0 0 1 1 1 3 0 4
0 0 6 2 4 3 -2 1

Output:
None
Square
Rhombus
Kite
Dart
Convex
Concave
Rectangle
Trapezoid
Rhomboid

Explanation: in the second test, the conditions for all types of convex quadrilaterals are matched. Since the square is the first in the priority list above, the correct answer is "Square".

Scoring

There are five set of tests, each set worth 2 points

Set 1 - first two types of quadrilaterals only, T = 20.
Set 2 - parallelograms only, T = 100.
Set 3 - convex types of quadrilaterals only, T = 500.
Set 4 - all types, T = 1000.
Set 5 - all types, T = 10000.