Largest Divisible Subset

You are given an array of positive integers. Your task is to find the size of the largest subset of the array such that for every pair of numbers \(x\) and \(y\) in the subset (with \(x \le y\)), \(y\) is divisible by \(x\). In other words, for every two numbers \(x\) and \(y\) in the subset, the condition \(y \mod x = 0\) must hold.

A typical approach is to sort the array and use dynamic programming to compute the largest valid subset ending at each element. Note that if the array is empty, the result should be 0.

Mathematical Formulation:
Given an array \(A\) sorted in non-decreasing order, find the maximum \(k\) such that there exists indices \(i_1, i_2, \dots, i_k\) with \(A[i_j] \mid A[i_{j+1}]\) for all \(1 \le j < k\).

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer \(N\), representing the number of elements in the array.
2. The second line contains \(N\) space-separated positive integers, the elements of the array. If \(N = 0\), the second line will be empty.

outputFormat

Output a single integer to standard output (stdout), which is the size of the largest divisible subset.

## sample

3
1 3 6

3

</p>