Background

Description

Count recursively the total number of "abc" and "aba" substrings that appear in the given string.

Format

Input

Output

Samples

abc

1

abcxxabc

2

abaxxaba

2

Limitation

1s, 1024KiB for each test case.