Description

一个只包含A，B，C三种字符的字符串，如果其中有连续的3个由A，B，C各一个组成的子串，则称这个字符串为fstring字符串。

例如：BAACAACCBAAA就是—个fstring与字符串，而AABBCCAABB则不是。

你的任务是计算只包含A，B，C三种字符且长度为n的这种字符串有多少个不是fstring字符串。

Input Format

Output Format

2

9

Source