Which Number Kind Is It?

Time limit2sMemory limit1024 MB

Summary

Given up to 100000 integers N up to 10^6, print O if N is odd, S if N is a perfect square, OS if both, and EMPTY otherwise.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

There are many number kinds out there, and you probably know some of them already. A few examples:

Odd number (O): $1, 3, 5, 7, 9, \ldots$
Square number (S): $0, 1, 4, 9, 16, 25, \ldots$

In this problem, you determine whether a given number $N$ is one of these special kinds. Print O if $N$ is odd, S if $N$ is a perfect square, and OS if $N$ is both odd and a perfect square. If $N$ is neither, print EMPTY.

Input

The first line contains an integer $T$ $(1 \leq T \leq 10^5)$ , the number of test cases. Each of the next $T$ lines contains a single integer $N$ $(0 \leq N \leq 10^6)$ .

Output

Print $T$ lines, one per test case. Each line contains O, S, OS, or EMPTY, as described above.

Examples1

Example 1
Input
```
4
1
7
20
9
```
Expected output
```
OS
O
EMPTY
OS
```