A string of letters , is forbidden if there are three consecutive letters from which one is , one is and one is . For example, is forbidden, while is not.
How many such strings of length are not forbidden?
Each line contains one number .
For each input value of print in a separate line the number of strings of length are not forbidden.