Nguyên vật liệu nhập về kho của một xí nghiệp được đóng trong các thùng giấy hình hộp chữ nhật. Để giải phóng chỗ người thủ kho phải xếp những hộp giấy rỗng lồng vào nhau cho gọn. Giả sử có ~N~ hộp giấy rỗng, các hộp được đánh số từ 1 đến ~N~. Với mỗi hộp giấy rỗng, người thủ kho biết được chính xác độ dài hai cạnh đáy của hộp là ~a~ và ~b~.

Yêu cầu: Hãy giúp người thủ kho xếp các hộp giấy rỗng sao cho trong số các dãy hộp giấy xếp chồng nhau ta được một dãy các hộp xếp chồng nhau có số hộp giấy lớn nhất có thể.

Input

• Dòng 1: Ghi số nguyên dương ~N~, là số lượng hộp giấy rỗng (~1 \le N \le 1000~).
• ~N~ dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương ~a_i, b_i~ cách nhau một khoảng trắng, là độ dài hai cạnh đáy của hộp giấy rỗng thứ ~i~ (~1 \le a_i, b_i \le 10000~).

Output

• Ghi ra số nguyên dương ~M~ là kết quả của bài toán.

Sample Input 1

5
1 5
5 7
6 4
3 6
2 5

Sample Output 1

3