[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

Jaimito didn't waste any time since he was offered his stones in 2013. He no longer spends his time playing with his mother Jimena to games in which his victory is guaranteed, for he explored many stone game variants, as every child should. He even became very good at some of these games, and took part in various championships obtaining excellent results.

For a few months now, he has been particularly interested in a game of stones called TArros con Piedras (TAP). In this game there are N jars with stones inside, and two players take turns to play. In his turn, each player should take one stone from one jar, two stones from another jar, and three stones from a third one, and so on until taking N stones from some jar, so that the player takes stones from every jar in a single turn. The game continues in this way until one of the players cannot take stones from the jars in a valid way in his turn. Said player loses the match, the other player being the winner.

For example, consider a match with N = 3 jars with one of them initially having P₁ = 3 stones, another one having P₂ = 4 stones and the third one having P₃ = 10 stones. In this match the player who starts playing has a winning strategy, as he can take one stone from the jar originally having ten stones, two stones from the jar which had three stones, and finally three stones from the jar that initially had four stones. He would then leave the jars with P₁ = 1, P₂ = 1 and P₃ = 9 stones, so that the second player cannot take stones from the jars in a valid way.

Jaimito is taking part in a TAP championship, and he has reached the finals, where he will face Jacinta. Both of them are expert players, so they make no mistakes when they play. Jaimito has told his mother everything about the match, i.e. the number N of jars and how many stones each of them will start with. Jimena knows Jacinta will start playing, and she would like to know if her son will win the championship, but she can't figure it out because she is too nervous to think properly. Can you help her?

Input

There are multiple test cases in the input file. For each test case, the first line contains an integer N representing the number of jars in the match (1 ≤ N ≤ 10⁵). The second line contains N integers P_i representing the number of stones in each jar before starting the match (1 ≤ P_i ≤ 10⁹ for i = 1, 2, ..., N).

Output

For each test case, print a line containing a charactner indicating if Jaimito will win the finals or not. The printed character should be an 'S' if Jaimito is to win, otherwise it should be an 'N'.

Example

Input:
3
3 4 10
2
10 3
Output:
N
S