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
2012-09-16 20:59:03 Francky
@tjandra : please choose one of C-flavour and disqualify others, it's not a good example given. You have ever been told about that.

Re by Tjandra: Done. I let my C99 solution because I use different I/O system, C99 doesn't support getchar_unlocked(). Sorry for the inconvenience.

Last edit: 2012-09-17 11:36:33
2012-09-16 18:09:39 (Tjandra Satria Gunawan)(曾毅昆)
easy problem, first try: AC 0.00s.
2012-06-25 19:14:17 Kumar Anurag
@RAJDEEP GUPTA, same here same solution using int gives WA while using long long int is AC.
2012-06-23 21:00:24 Sardar Khan
easy :)
2012-06-22 11:03:12 Mukul
More test cases please.....
2012-06-06 06:44:48 Mr. Rook
you dont need long long .
int will work
2012-05-29 09:09:10 jaans
i was getting tle first,,, i made a single change and guess what..AC (0.03s) :D
2012-01-03 08:19:26 Jitesh
Can nyone post some more test cases.....I don't know why m I getting a WA even sfter using long long int.....
2011-10-10 15:57:51 accept
simple problem
2011-09-25 18:51:22 RAJDEEP GUPTA
Use long long int(for the answer) in C.
I got WA for using int.
Got AC after using long long int.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.