Chef and Square Set

Chef is teaching his students about properties of integers. Today he is teaching them about numbers which are squares of some number, e.g. 1, 4, 9, 16, 25 etc. These numbers are said perfect squares. He gave his students the following task as homework. He gives an array a consisting of n positive integers. He calls the array w0w if for every pair of indices i, j, the product ai * aj is a perfect