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