The king found his adherents were building four sanctuaries for him. He is interested about the positions of the sanctuaries and wants to know whether they would form a parallelogram, rectangle, diamond, square or anything else.

Input

The first line of the input is T(1 <= T <= 1000), which stands for the number of test cases you need to solve.
Each case contains four lines, and there are two integers in each line, which shows the position of the four sanctuaries. And it is guaranteed that the positions are given clockwise. And it is always a convex polygon, if you connect the four points clockwise.

Output

For every test case, you should output "Case #t: " first, where t indicates the case number and counts from 1, then output the type of the quadrilateral.

Sample Input

5
0 0
1 1
2 1
1 0
0 0
0 1
2 1
2 0
0 0
2 1
4 0
2 -1
0 0
0 1
1 1
1 0
0 0
1 1
2 1
3 0

Sample Output

Case #1: Parallelogram
Case #2: Rectangle
Case #3: Diamond
Case #4: Square
Case #5: Others


这个题不是自己写的 基础集合 判断四个点构成什么图形 据队友说 要考虑斜率为0和无穷大的情况

#include <iostream>
#include <cstdio>
using namespace std;
struct point{
    int x,y;
}p[4];
int chang(point a,point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int kab,kbc,kcd,kda,ablen,bclen,cdlen,dalen;
bool jud1(){
    return (p[1].y-p[0].y)*(p[2].x-p[3].x)==(p[2].y-p[3].y)*(p[1].x-p[0].x);
}
bool jud2(){
    return (p[3].y-p[0].y)*(p[2].x-p[1].x)==(p[2].y-p[1].y)*(p[3].x-p[0].x);
}
bool jud3(){
    if(p[1].x==p[0].x&&p[3].y==p[0].y) return 1;
    if(p[1].y==p[0].y&&p[3].x==p[0].x) return 1;
    return ((p[1].y-p[0].y)*(p[3].y-p[0].y)+(p[1].x-p[0].x)*(p[3].x-p[0].x))==0;
}
bool jud4(){
    return ablen==bclen&&bclen==cdlen&&cdlen==dalen;
}
int main()
{
    int t,ca=1;
    cin>>t;
    while(t--){
        for(int i=0;i<4;i++){
            scanf("%d%d",&p[i].x,&p[i].y);
        }
        //kab=xie(p[0],p[1]),kbc=xie(p[1],p[2]),kcd=xie(p[2],p[3]),kda=xie(p[3],p[0]);
        ablen=chang(p[0],p[1]),bclen=chang(p[1],p[2]);
        cdlen=chang(p[2],p[3]),dalen=chang(p[3],p[0]);
        printf("Case #%d: ",ca++);
        if(jud1()&&jud2()&&jud3()&&jud4()){
            puts("Square");
        }
        else if(jud4()){
            puts("Diamond");
        }
        else if(jud1()&&jud2()&&jud3()){
            puts("Rectangle");
        }
        else if(jud1()&&jud2()){
            puts("Parallelogram");
        }
        else puts("Others");
    }
    return 0;
}