Trên hệ trục toạ độ Oxy có một con Robot đang đứng tại vị trí gốc toạ độ (0, 0). Robot có thể di chuyển 1 ô đơn vị.

Ban đầu Robot sẽ đi đến 1 ô trong 4 vị trí xung quanh, từ bước đi thứ 2 trở đi, Robot có thể Tiến-Lùi-Rẽ trái-Rẽ phải 1 đơn vị.

Trong ví dụ ở hình bên, từ ô (0,0), robot đi đến (1,0), rẽ trái sang ô (1,1), rẽ phải sang ô (2,1), rẽ phải sang ô (2, 0), rẽ trái sang (3,0) cuối cùng rẽ phải sang ô (3, - 1).

Cho toạ độ những điểm mà Robot đã đi qua, hãy viết một chương trình tính số lần mà Robot này đã rẽ phải.
Input

Dòng đầu tiên là số lượng testcase T của bài toán (1 <= T <= 100)

Dòng đầu tiên của mỗi testcase là số tự nhiên N (3 <= N < 10.000) cho biết số lượng điểm mà Robot đã đi qua.

N dòng tiếp theo, mỗi dòng chứa 2 số nguyên (x, y) cho biết toạ độ những điểm mà Robot đã đi qua.

Output

Mỗi tescase được in trên 1 dòng với: bắt đầu bằng ký tự "#", tiếp theo là một dấu cách (khoảng trắng), và cuối cùng là kết quả của testcase đó.

Example

Input:
1
7
0 0
1 0
1 1
2 1
2 0
3 0
3 -1

Output:
#1 3