Cho tập số nguyên dương $𝑆 = {𝑎_1, 𝑎_2, … , 𝑎_𝑛}$. Hãy tìm một tập con $𝐷$ của $𝑆$ gồm nhiều số nhất mà hai phần tử $𝑥, 𝑦$ bất kì thuộc tập $𝐷$ thì hoặc là $𝑥$ chia hết cho $𝑦$ hoặc là $𝑦$ chia hết cho $𝑥$.

Input

• Dòng đầu chứa số nguyên dương $𝑛$;

• Dòng tiếp theo chứa $𝑛$ số nguyên dương mô tả tập $𝑆$ (các số không vượt quá $10^{18}$).

Output

• Gồm một dòng chứa một số là lực lượng tập $𝐷$ tìm được. $|D|$: Lực lượng tập $D$

Sample Input

4 
6 9 12 3

Sample Output

3

Giới hạn

Subtask 1: n ≤ 20; 
Subtask 2: n ≤ 200;