# A Multiplication Game

Shohei and Naoki play the game of multiplication by multiplying an
integer *p* by one of the numbers 2 to 9. Shohei always starts
with *p* = 1, does his multiplication, then Naoki multiplies
the number, then Shohei and so on. Before a game starts, they draw
an integer 1 < *n* < 4,294,967,295 and the winner is whoever
reaches *p* ≥ *n* first.

## Input File: multiply.in

Each input line contains a single integer *n*.

## Output File: multiply.out

For each line of input, output one line - either

Shohei wins.

or

Naoki wins.

## Sample Input

162
17
34012226

## Sample Output

Shohei wins.
Naoki wins.
Shohei wins.