Trên hệ tọa độ \(Oxy\) có \(n\) điểm, hãy tìm cách vẽ lên số đường thẳng ít nhất, sao cho mỗi điểm trong \(n\) điểm này đều thuộc ít nhất một đường thẳng.

Input

• Số nguyên dương \(q\) --- số câu hỏi
• Mỗi câu hỏi chứa số nguyên dương \(n\), và tọa độ \(x_i\), \(y_i\) của \(n\) điểm

Constraints

• \(q \leq 500\)
• \(n \leq 16\)
• \(-10^5 \leq x_i, y_i \leq 10^5\)

Output

• Với mỗi test case, in ra một dòng dạng Case X: Y trong đó \(X\) là số thứ tự test case và \(Y\) là số đường thẳng ít nhất cần vẽ

Example

2
3
0 0
1 1
2 2
3
0 0
1 1
2 3

Case 1: 1
Case 2: 2

Tham khảo: LightOJ