GUESSTHE - Guess the Number

You are playing the funny game “Guess the number” with a friend. In this game, one of the players choose a positive integer and the other has to guess it by using the clues that are revealed. The i-th clue is either “Y” or “N” indicating whether the hidden number is a multiple of i or not, respectively. For instance, if the clues so far are “YYNYY” it means that the number is a multiple of 1, 2, 4 and 5, but it is not a multiple of 3. Given the clues of the game so far, you have to guess the minimum possible number according to them, or call your friend a cheater if there is no number such that the clues were correctly given.

Input

The input contains several test cases. Each test case is described in a single line that contains a non-empty string of at most 20 characters. The string is formed entirely of uppercase letters “Y” and “N”, and represents the clues given so far, in order from left to right. The last line of the input contains a single asterisk and should not be processed as a test case.

Output

For each test case output a single line with the minimum positive integer that satisfies all the clues, or −1 if there is no such a number.

Example

Input:
YYNYY
YYYNNN
*

Output:
20
-1

Added by:Pablo Ariel Heiber
Date:2010-08-19
Time limit:2.950s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2008

hide comments
2024-03-15 04:43:17
YYYYYYYYYYYYYYYYYYYY
*

232792560
2017-12-04 19:34:07
Easy problem, AC in one go!!
2017-07-03 12:04:05
int cost me 1wa use long long. simple lcm problem, see geeksfor geeks for lcm algo
2017-06-28 10:37:47
use long long int ....else it will give wa...faced many such wa's due to it
2016-01-30 07:39:37
AC 0.00 Easy one! ;)

Last edit: 2016-01-30 07:40:06
2015-07-18 12:38:58 Dushyant Singh
@headfirstcoder: There are at max 20 characters only. Problem may arise if you are not considering \0 in character array.
@ Harshit : It depends how user calculates the answer. In one case there will be overflow and in the other there will be no overflow.
2015-06-18 05:44:45 [Mayank Pratap]
Completed Double century by some guess work ... :P
2015-05-30 17:40:57 ---@@@----
AC after lot of WA's cause of silly mistake..
Otherwise its easy one..
2015-05-10 08:17:44 nap11
what will be the max length of string?
2015-03-06 23:13:24 Vaporeon
GOT WA FOR DECLARING STRING SIZE AS 20.. AC(0.00 SEC) AFTER INCREASING SIZE TO 100.. :3 :X

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.