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 of integers. Select two elements from the array, Let’s assume they are and . Now make a grid size of . 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 grid.
Observe the example:
Let’s say
If you select , and ;
Now you can cover the graph in two ways.
So, there exist two different sizes of tiles for covering the grid, .
If we would select a grid or a grid, we couldn’t use more than one type of tile in those grids.
The first line will be a single integer — indicating the size of the array.
The following line will contain integers is separated by spaces — indicating the elements of the array .
For each test case, out an integer which is the maximum number of distinct squared-shaped tiles you can use for any grid.
Input | Output |
---|---|
6 8 1 2 16 4 16 | 5 |
Input | Output |
---|---|
3 1 4 6 | 2 |