Description

由于嫉妒Mirko村长的职位，Borko 冲进他的帐篷，试图用一个诡计来证明Mirko在领导方面的无能。 Borko 将三个不透明的杯子并排放在桌子上（开口朝下），在最左边的杯子下面放一个小球。然后，他以三种可能的方式之一多次交换两个杯子。Mirko 必须告诉球最终在哪个杯子下。

聪明的Mirko 双手交叉微笑，Borko 努力让杯子越来越快地移动。Borko 不知道的是，后面的程序员正在记录他的所有动作，请你编写一个程序通过记录的Mirko的移动动作来确定球的位置。

Format

Input

输入一行字符串，其中每个字符都是“A”、“B”或“C”（不带引号），即 Borko 的动作。

Output

输出球所在杯子的索引：1表示在左杯子下面，2表示在中间杯子下面，3表示在右杯子下面。

Samples

AB

3

ABCAACBABCAACBACCCCAABCBBAACCCACABAA

3

Limitation

对于100%的数据：输入的字符串长度<=10000。