Multiple Switches

Interview

Time limit2sMemory limit512 MB

Summary

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

Level: Medium5 of 10
Topics: Greedy, Math, Number theory, Implementation
Solved: No attempts yet

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.

Examples4

Example 1
Input
```
YYYYYY
```
Expected output
```
1
```
Example 2
Input
```
YNYNYNYNY
```
Expected output
```
2
```
Example 3
Input
```
NNNNNNNNNN
```
Expected output
```
0
```
Example 4
Input
```
YYYNYYYNYYYNYYNYYYYN
```
Expected output
```
4
```