XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: selos.x, onde x deve ser c, cpp, java, js ou py

Selos

Euclides é um garoto que gosta muito de colecionar selos. No seu aniversário, seus pais o presentearam com N selos, todos em formato de quadrados com 1 cm de lado. Euclides gostaria de guardar todos os N selos que ganhou colando-os numa página de papel em branco. Ao decidir por guardá-los assim, no entanto, ele logo percebeu que a única forma que lhe agradava de posicionar os selos na página era a forma de um retângulo completamente coberto pelos mesmos, sem sobreposição.

Ele percebeu também que, independente do número de selos obtido, colocar todos os selos numa única linha ou todos os selos numa única coluna é uma configuração válida. Como essa maneira usa a página do caderno de um jeito muito ineficiente, Euclides gostaria de saber se existe algum modo de dispor os N selos num retângulo que tenha mais de uma linha e mais de uma coluna tal que todas as linhas e colunas sejam completamente ocupadas por selos (isto é, tal que não existam posições sem selos no interior do retângulo).

Entrada

A entrada contém uma única linha com um único inteiro N, o número de selos que Euclides ganhou.

Saída

A saída deve conter uma linha com um único caracter, que deve ser "S" se for possível organizar os selos em um retângulo com mais que uma linha e mais que uma coluna ou "N" caso não seja possível.

Restrições

  • 1 ≤ N ≤ 10 000 000 000.

Informações sobre a pontuação

  • Em um conjunto de casos de teste que totaliza 70 pontos, N ≤ 1 000 000.

Exemplos

Entrada
8
			
Saída
S
			

A figura abaixo exemplifica duas maneiras de guardar os selos em forma de retângulo.

Entrada
1
			
Saída
N
			
Entrada
11
			
Saída
N
			
Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação