Challenging Case

Limits 1s, 512 MB

Officer Rahman, a mysterious character, often gets into trouble. He faced the most dangerous criminals and emerged victorious on every occasion. His fellow officers marveled at his abilities, but OC Rahman merely shrugged and declared, "OC Rahman never loses."

Once again, OC Rahman found himself in deep trouble, facing the most challenging case of his lifetime. Aware of his undefeated record against criminals, he divided the case into smaller parts to shorten its complexities. Regrettably, one part required mathematical and programming skills. Being the renowned programmer in town, OC Rahman seeks your assistance to overcome this obstacle.

The problem is, You are given an array AA of nn integers. Select two elements from the array, Let’s assume they are NN and MM. Now make a grid size of N×MN\times M. You have to cover the total grid using some square size of tiles. No cell can be blank and no cell can be covered twice.

A tile of square shape will be valid if you can cover the total grid using that tile only. Assume you have infinite number of tiles with infinite number of squared shapes.

Your task is to find the maximum number of distinct squared-shaped tiles you can use for any N×MN\times M grid.

Observe the example:

Let’s say A=[1,4,6]A = [1, 4, 6]

If you select M=4M = 4, and N=6N = 6;

Now you can cover the 4×64\times 6 graph in two ways.

So, there exist two different sizes of tiles for covering the grid, N×MN\times M.

If we would select a 1×41\times 4 grid or a 1×61\times 6 grid, we couldn’t use more than one type of tile in those grids.

Input

The first line will be a single integer nn (2n512)\: (2\le n\le 512) — indicating the size of the array.

The following line will contain nn integers A1,A2,A3..,AnA_1, A_2, A_3…..,A_n(1A[i]105)\: (1\le A[i]\le 10^5) is separated by spaces — indicating the elements of the array AA.

Output

For each test case, out an integer which is the maximum number of distinct squared-shaped tiles you can use for any N×MN\times M grid.

Samples

InputOutput
6
8 1 2 16 4 16
5
InputOutput
3
1 4 6
2