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;