最小下标

小蓝有一个由大写字母ABCDEF组成的字符串S，长度为n，字符串的下标依次为0到n-1。

小蓝按照如下方法生成一个无限长的字符串：

首先选定一个0到n-1之间的数，作为初始下标。

从初始下标开始，将下标对应的字符加入到字符串的结尾，将字符的序号（A到F依次对应1到6）与下标相加作为新的下标值，如果下标大于等于n，将其对n求余。重复此过程，即得到无限长的字符串。例如，对于字符串ACDF，当初始下标是0时，生成的字符串为：ACACACACAC...

再如，对于字符串DCBA，当初始下标是1时，生成的字符串为：CDDDDDDDDD.…

给定小蓝的字符串S，请问当初始下标为多少时，生成的字符串最小。

输入格式

输入一行包含一个字符串。

输出格式

输出一行，包含一个整数，为所求的下标，如果有多个下标满足要求，输出最小的那个。

样例输入1

DCBA

样例输出1

3

样例输入2

AAAA

样例输出2

0

评测用例规模与约定

令|S|表示S的长度。

对于30%的评测用例，1<=|S|<=100。

对于50%的评测用例，1<=|S|<=1000。

对于70%的评测用例，1<=|S|<=10000。

对于80%的评测用例，1<=|S|<=100000。

对于所有评测用例，1<=|S|<=1000000。