Farmer John ha comprato un elegante trattore nuovo programmabile. Inserisce una stringa di lunghezza $N$, $1 \le N \le 100,000$, solo con F, $L$ e $R$. F avanza di un'unità, $L$ e $R$ girano rispettivamente a sinistra e destra di $90^\circ$. Parte dall'origine $(0,0)$ rivolto a nord.
Dopo aver inserito la stringa prevista, FJ ricorda di aver sbagliato esattamente un carattere, ma non quale! Ad esempio F o $L$ al posto di $R$. Conta le posizioni finali diverse possibili nel piano (la direzione finale non conta).
Input
- Riga 1: la stringa di comandi prevista da Farmer John.
Output
- Riga 1: numero di posizioni finali con un carattere sbagliato.
Esempi
Input 1
FF
Output 1
3
Nota
Farmer John vuole avanzare due volte, idealmente fino a $(0,2)$.
Le quattro stringhe errate sono FL, FR, LF, RF, con posizioni finali rispettive $(0,1)$, $(0,1)$, $(-1,0)$, $(1,0)$: tre posizioni diverse.
Autore del problema: Brian Dean, 2012