Largest Divisible Subset

Given an array of n positive integers, your task is to find the largest subset in which every pair of elements \(S_i\) and \(S_j\) satisfies the divisibility condition: either \(S_i \mid S_j\) or \(S_j \mid S_i\) (i.e. one divides the other without remainder). In other words, for every two numbers \(a\) and \(b\) in the subset, at least one of the conditions a % b = 0 or b % a = 0 must hold.

Note: Here, the symbol \(\mid\) is used to denote divisibility. The input consists of an integer followed by a series of integers. Your program should output the size of the largest divisible subset.

Constraints:
1 \(\le n \le 1000\)
Each integer in the array is a positive integer not exceeding \(10^9\).

inputFormat

The first line of input contains an integer n, representing the size of the array. The second line contains n positive integers separated by spaces.

outputFormat

Output a single integer which is the size of the largest subset of the array where for every pair of elements, one is divisible by the other.

6
1 2 3 4 8 16

5