«QAQ» — смайлик, используемый для выражения плача. Представьте, что «Q» — это глаза со слезами, а «A» — рот.
Алмаз дал Борту строку, состоящую только из заглавных букв латинского алфавита длины n. В строке содержится большое число «QAQ» (Алмаз так мил!).
Борт хочет узнать, сколько подпоследовательностей «QAQ» встречаются в строке, которую дал Алмаз. Обратите внимание, буквы «QAQ» не обязательно должны идти непосредственно друг за другом, но порядок букв должен быть соблюден.
Выходные данные
Выведите одно целое число — количество подпоследовательностей «QAQ» в строке.
Примечание
В первом примере 4 подпоследовательностей «QAQ»: «QAQAQYSYIOIWIN», «QAQAQYSYIOIWIN», «QAQAQYSYIOIWIN», «QAQAQYSYIOIWIN».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
QAQAQYSYIOIWIN
|
4
|
|
2
|
QAQQQZZYNOIWIN
|
3
|