Cho ~n~ điểm trong hệ tọa độ Descartes ~2D~. Bạn phải tính số lượng đa giác lồi có lớn hơn hoặc bằng ~3~ đỉnh mà có thể tạo thành bằng cách chọn một tập hợp con trong tập hợp các điểm đã cho. Để đơn giản, dữ liệu vào đảm bảo các điều kiện sau:

• Không có ~3~ điểm bất kỳ nào thẳng hàng.
• Không có ~2~ điểm nào có cùng tọa độ.

Do kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho ~1234567~

Input

Dòng đầu chứa số nguyên ~T~, số lượng test. Trong mỗi test:

• Dòng đầu chứa ~n~ là số lượng điểm của test đó;
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên là tọa độ của điểm thứ ~i~. Trị tuyệt đối của các tọa độ không quá ~10000~.

Output

~T~ dòng, mỗi dòng ghi đáp án cho test tương ứng.

Giới hạn

Input Set ~1~: ~T \leq 100;\text{ }3 \leq n \leq 10~.

Input Set ~2~: ~T \leq 50;\text{ }3 \leq n \leq 100~.

Sample Input

2
4
0 0
2 0
2 2
0 2
6
0 0
2 0
2 2
0 2
1 -1
1 3

Sample Output

5
42