一个只包含'A'、‘B’、‘C’的字符串，如果存在某一段长度为3的连续子串中恰好‘A’、‘B’、‘C’各有一个，那么这个字符串就是纯洁的，否则这个字符串就是暗黑的。

例如：

BAACAACCBAAA 连续子串'CBA'中包含了‘A’、‘B’、‘C’各一个，所以为纯洁字符串.

AABBCCAABB 不存在一个长度为3的连续子串包含‘A’、‘B’、‘C’，所以为暗黑字符串.

你的任务就是计算出长度为n的字符串(只包含‘A’、‘B’和‘C’)，有多少个是暗黑字符串。

输入一整数n，表示字符串长度为(1<=n<=30)

输出一个整数表示有多少个暗黑字符串

2

9