Chef has bottles of several capacities. He likes to note down, for each bottle, those smaller amounts that he can use to exactly divide its contents. He calls these amounts “helper amounts”.
For example, the helper amounts of a 21 L bottle are 1 L (since he can use 21 of these to divide the contents), 3 L (he can use 7 of these), and 7 L (he can use 3 of these). Similarly, a 20 L bottle has helper amounts 1, 2, 4, 5, and 10 L.
Now, Chef is superstitious and is scared of some bottles. A “spooky bottle” must satisfy two conditions. First, all of its helper amounts must have a sum strictly greater than the bottle’s capacity. Second, if Chef chooses any subset of its helper amounts, the sum must never equal the bottle’s capacity.
Chef thinks that his new shipment might have spooky bottles and is too scared to check them himself, so he calls you instead. Input
The first line has an integer T indicating the number of bottles. It is followed by T lines, each containing the capacity N of a bottle. Output
For each bottle, output a line containing SPOOKY if it is spooky or OK if it is not. Constraints 1 = T = 5001 = N = 100000 Example Input: 2 20 70 Output: OK SPOOKY
Example case 1.
20’s helper amounts are [1, 2, 4, 5, 10] which add up to 22. The first condition is satisfied. Furthermore the subset [1, 4, 5, 10] adds up to 20, hence the second condition is violated. So 20 is not spooky.
Example case 2.
70’s helper amounts are [1, 2, 5, 7, 10, 14, 35] which add up to 74. The first condition is satisfied. Furthermore no subset of the amounts adds up to 70. The second condition is satisfied. So 70 is spooky.