Cho dãy ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (các phần tử được đánh chỉ số từ ~1~ đến ~n~, hai phần tử bằng nhau ở hai vị trí khác nhau được coi là phân biệt). Tập con ~S~ của dãy được gọi là thuần khiết nếu mọi phần tử trong ~S~ đều là ước của phần tử lớn nhất trong ~S~. Ví dụ: Với dãy số ~\{2, 3, 4\}~: Có các tập con ~\{2\}~; ~\{3\}~; ~\{4\}~; ~\{2, 3\}~; ~\{2, 4\}~; ~\{3, 4\}~; ~\{2, 3, 4\}~. Trong đó các tập ~\{2\}~; ~\{3\}~; ~\{4\}~; ~\{2, 4\}~ là tập thuần khiết.

Yêu cầu: Hãy tính kích thước lớn nhất của một tập thuần khiết là tập con của dãy đã cho (kích thước của tập con là số lượng các phần tử thuộc tập).

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^{18}, 1 \le i \le n)~.

Các số trên một dòng cách nhau bởi một dấu cách.

Output

Ghi ra một số nguyên là kích thước lớn nhất của tập thuần khiết tìm được.

Scoring

Sample Input 1

6
2 3 6 12 4 9

Sample Output 1

5

Sample Input 2

5
2 3 5 7 11

Sample Output 2

1

Notes

• Với dãy số ~\{2, 3, 6, 12, 4, 9\}~: xét tập con ~\{2, 3, 4, 6, 12\}~ có phần tử lớn nhất là ~12~, các phần tử trong tập con đều là ước của ~12~. Vậy tập con ~\{2, 3, 4, 6, 12\}~ là tập thuần khiết và có kích thước là ~5~ thỏa mãn yêu cầu.

• Tất cả các số trong ví dụ thứ hai là nguyên tố phân biệt, không có hai số nào theo quan hệ "một số là ước của số lớn hơn". Kích thước lớn nhất là ~1~.