Son muy conocidos los números de Fibonacci y la forma en que se forman dichos números. El problema que se nos plantea ahora tiene mucho que ver con el anterior lo que ahora este se extiende hasta formar las cadenas de Fibonacci las cuales se definen de la siguiente manera:

Sean ~S_1~ y ~S_2~ dos caracteres (entre “a” y “z”).

La \(k-ésima\) cadena de Fibonacci ~(k > 2)~ se define como:

~S_k = S_k-1 S_k-2~ para ~k > 2~ es decir concatenando las dos cadenas de Fibonacci anteriores.

Ejemplo:

~S_1 =~ abc

~S_2 =~ xyz

~S_3 = S_2 S_1 =~ xyzabc

~S_4 = S_3 S_2 =~ xyzabcxyz

….

Y así sucesivamente.

Se dice que una cadena ~x~ es sufijo de la cadena ~S~ si ~S~ termina con ~x~.

Sean ~S~ y ~S_k~ cadenas de caracteres, se dice que ~S_k~ es sufijo de ~S~, si para alguna cadena ~w~ se obtiene ~S = w S_k~.

Nuestro problema consiste en dada una cadena ~S~ determine cuál es el mayor ~K~ tal que la cadena de Fibonacci ~S_k~ sea sufijo de la cadena ~S~ dada.

Tarea

Hacer un programa que permita:

• Leer desde la entrada estándar la cadena ~S~ y los dos caracteres iniciales de la secuencia de Fibonacci.

• Determinar el mayor valor de ~K~ tal que la cadena Fibonacci ~S_k~ sea sufijo de la cadena ~S~.

• Escribir hacia la salida estándar el valor de ~K~, o el dígito cero en caso de que no exista ningún ~S_k~ que sea sufijo de la cadena ~S~ dada.

Entrada

• Línea 1: El carácter ~S_1~.

• Línea 2: El carácter ~S_2~.

• Línea 3: ~N (1 \leq N \leq 10 000)~, cantidad de caracteres de la cadena ~S~.

• Línea 4…N+3: En cada una de estas líneas se escribirá un carácter de la cadena ~S~.

Salida

• Una sola línea en la que se escribirá el valor ~K~.

Ejemplo de Entrada 1

a
b
8
s
a
g
b
a
b
b
a

Ejemplo de Salida 1

5

Ejemplo de Entrada 2

a
x
10
e
j
e
m
p
l
o
x
b
c

Ejemplo de Salida 2

0