Một hệ thống siêu máy tính đang tiếp nhận danh sách gồm ~N~ gói tác vụ từ các tổ chức cần lập lịch thực thi (có tối đa ba tổ chức). Gói tác vụ thứ ~i~ của tổ chức ~A_i~ yêu cầu ~C_i~ lõi vi xử lý (CPU) và ~R_i~ gigabyte bộ nhớ RAM.

Để bộ điều phối phần cứng có thể tối ưu hoá luồng xử lý, ta cần chọn chuỗi tác vụ sao cho nhu cầu tài nguyên CPU và RAM của tác vụ sau luôn lớn hơn tác vụ trước. Nói cách khác, chọn một chuỗi ~K~ tác vụ ~(i_1,i_2,\dots,i_K)~ thoả mãn quy tắc sau:

~C_{i_1} < C_{i_2} < \dots < C_{i_K}~ và ~R_{i_1} < R_{i_2} < \dots < R_{i_K}~.

Để giữ tính cân bằng giữa các tổ chức, chuỗi tác vụ được chọn đảm bảo không có ba tác vụ liên tiếp thuộc cùng một tổ chức.

Yêu cầu: Hãy xác định độ dài chuỗi tác vụ hợp lệ dài nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^5)~;

• ~N~ dòng sau, dòng thứ ~i~ gồm ba số nguyên dương ~C_i,R_i,A_i~ ~(1 \le C_i,R_i \le 10^{18}; 1 \le A_i \le 3)~.

Dữ liệu đảm bảo không có ~2~ bộ ~C_i,R_i,A_i~ giống nhau.

Output

• Một số nguyên là kết quả của bài toán.

Scoring

Sample Input 1

8
3 3 1
4 3 2
9 8 3
1 1 1
9 8 1
5 6 1
7 8 2
7 7 1

Sample Output 1

5

Notes

Có thể thực hiện các tác vụ như sau:

• ~[1,1,1]~

• ~[4,3,2]~

• ~[5,6,1]~

• ~[7,7,1]~

• ~[9,8,3]~