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;