C. Cities in Sao Paulo
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This year is the first year of the Paulista Programming Marathon, and its organizers are creating several programs to help organize the event. Wilson is suspecting that universities from cities outside the state of São Paulo will also want to officially participate in the event, as everyone is excited about this new programming marathon. However, only cities from the state of São Paulo can officially participate.

Wilson is so suspicious that he obtained approximate integer coordinates of the registered cities as if they were points on a Cartesian plane. In this approximate model, the state of São Paulo is geometrically drawn as the following polygon, as shown in the image: $$$(0, 100)$$$, $$$(100, 0)$$$, $$$(200, 0)$$$, $$$(100, -100)$$$, $$$(0, -100)$$$, $$$(-100, 0)$$$, $$$(-200, 0)$$$, $$$(-100, 100)$$$.

Now Wilson wants to make a program that checks which cities are inside or on the edge of this polygon to determine which cities are really in the state of São Paulo, but he is not good at geometry and asked for your help.

Input

The first line contains an integer $$$N$$$ representing the number of cities $$$(1 \le N \le 100)$$$. In the following $$$N$$$ lines, two integers $$$x$$$ and $$$y$$$ are given, representing the coordinates of each city $$$(-1000 \le x, y \le 1000)$$$.

Output

The output should contain $$$N$$$ lines with only one character to respond in order about each of the cities given in the input, 'S' if the point representing the city is inside or on the edge of the polygon representing the state of São Paulo, or 'N' otherwise.

Examples
Input
3
0 0
100 50
100 -50
Output
S
N
S
Input
5
0 100
1 100
0 99
-1 100
0 101
Output
S
N
S
S
N