DNA sequence

Time Limit: 1000ms

Memory Limit: 65536KB

Description

  N博士发现了一个奇妙的基因序列:将这种序列移植到酵母菌中,可以制造出一种能量饮品,据说能打破中国队TI冠军的局面。作 为自由国度的一名科学家,N博士迫切地想大规模产生这种基因序列。   基因工程中基因复制遵循一定的法则:   (1)复制皿每一轮会无条件复制出原序列a倍长的序列 如原序列S0 :AT ,在a=3时,经过第一轮生成S1: AT-AT-AT ,在不考虑酶作用前提下,再经过一轮,重复上一次操作,第二轮得到S2 : ATATAT-ATATAT-ATATAT   (2) 生物学家可以根据目标基因制造出一种特殊的切割酶,总是固定从头开始(必须从头开始)切割;每次水解长度 k*strlen(S0) 的 DNA序列,水解掉的序列不会再参与后续增殖,直到剩余序列小于k*strlen(S0) .   已知整个过程中,水解酶始终在作用,保证不会有超过 k*strlen(S0)长度的序列存在   现在,已知目标DNA序列为S,同时生物学家可以初始合成任意的DNA序列S0,但是直接合成的成本极大。因此在保证能大批量产生S 序列的前提下,N博士希望尽可能的使用较短的S0序列。那么对于最短可实现批量复制的S0,请你帮N博士计算一下,最少经过多少轮就可以得到目的序列。为了保证能够生成序列,这里gcd(a,k)=1。

Input

  输入包含多组用例,以读到文件末尾结束。   每组第一行输入一个字符串,由ATCG组成,代表目标DNA序列S。S长度小于10^6   第二行包括两个整数,a,k (1<=a,k<=10^9 )。a代表复制皿每次复制序列长度与原长度比,k代表对于N博士选定的S0,酶每次切割k 倍长度的S0

Output

  输出一行,代表在。因此对于能实现大批量产生S序列的最短的S0,第一次生成S所需要的最短复制的次数n 注意n不可以为0或者1。

Sample Input

ATATATATATAT
3 7

Sample Output

3

Hint

None

Source

None

提交代码