CZ-SK-MO 2010 Problem 5

On the board are written numbers $1, 2,. . . , 33$ . In one step we select two numbers written on the product of which is the square of the natural number, we wipe off the two chosen numbers and write the square root of their product on the board. This way we continue to the board only the numbers remain so that the product of neither of them is a square. (In one we can also wipe out two identical numbers and replace them with the same number.) Prove that at least $16$ numbers remain on the board.