“QAQ”是表示哭泣的表情的词。将“Q”想象为含泪的眼睛,将“A”想象为一张嘴。
现在 Diamond 给了 Bort 一个仅由大写英文字母组成、长度为 n 的字符串。字符串中有很多“QAQ”(钻石太可爱了!)。
猫屋插图 https://twitter.com/nekoyaliu
Bort 想知道 Diamond 给出的字符串中有多少个子序列“QAQ”。请注意,字母“QAQ”不必是连续的,但字母的顺序应该准确。
输入
唯一一行包含长度为 n (1 ≤ n ≤ 100) 的字符串。保证字符串只包含大写英文字母。
输出
打印单个整数 - 字符串中子序列“QAQ”的数量。
示例
输入 #1
QAQAQYSYIOIWIN
输出 #1
4
输入 #2
QAQQQZZYNOIWIN
输出 #2
3
注意
在第一个示例中,有 4 个子序列“QAQ”:“QAQAQYSYIOIWIN”、“QAQAQYSYIOIWIN”、“QAQAQYSYIOIWIN”、“QAQAQYSYIOIWIN”。