Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS12QUAD - O-Quadrilaterals

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.


Added by:Tata Dule
Date:2012-12-08
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV ICK JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.