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.