Multiple Switches

Given N bulbs as Y/N, find the fewest presses of switches that flip multiples to turn all bulbs off, or -1 if impossible.

Medium5GreedyMathNumber theoryImplementationInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples4

Problem

There are $N$ light bulbs in a row, numbered 1 through $N$ . Each bulb is either on or off.

There are also $N$ switches, numbered 1 through $N$ . Pressing switch $i$ flips every bulb whose number is a multiple of $i$ : a bulb that was on turns off, and a bulb that was off turns on. You may press the same switch more than once.

Given the current state of the bulbs, write a program that finds the smallest number of switch presses that turns every bulb off.

Input

The first line contains the state of the bulbs, starting from bulb 1. A bulb that is on is written as Y, and a bulb that is off is written as N.

The number of bulbs $N$ satisfies $1 \le N \le 1\,000$ .

Output

Print the smallest number of switch presses that turns every bulb off. If no sequence of presses turns every bulb off, print -1.