Ben's favorite hobby is puzzles such as Heyawake or Nurikabe. Sadly, he has solved every puzzle that exists, so Nic has decided to create a new one for him. In this puzzle, Nic will lay out some cards, each with a positive or negative integer written on its top face (note that zero will not appear on any cards). Ben then must choose some (possible none) of the cards such that no non-empty subset of chosen cards has a product whose absolute value is a perfect square. Ben must also optimize the set of cards he chooses, first maximizing the number of cards he chooses, then maximizing the product of the integers on the cards. The product of the empty set is defined to be $$$1$$$.

As Nic commonly claims, "surely puzzle boy can puzzle it out," and indeed he did. Ben solves these puzzles with such ease that Nic doesn't even have time to verify Ben's answer! Thus, Nic has asked you to write a program that computes the maximum product that Ben can achieve. To make the calculations easier, Nic has guaranteed that each integer written on a card can be expressed as the product of integers between $$$-1000$$$ and $$$1000$$$, inclusive.