Una máquina recibe instrucciones \((s, n)\), con \(s\) un texto no vacío y \(n \ge 1\), e imprime \(n\) caracteres: el \(i\)-ésimo (desde \(0\)) es \(s_{i \bmod |s|}\). Por ejemplo, \((\texttt{ab}, 4)\), \((\texttt{cd}, 3)\), \((\texttt{xx}, 2)\) imprimen ababcdcxx.

Solo se permiten textos \(s\) de largo a lo más \(D\). Calcula la mínima cantidad de instrucciones para imprimir exactamente el texto \(T\).

Entrada

Una línea con el texto \(T\), de letras minúsculas, seguido del entero \(D\) \((1 \le D \le |T| \le 2 \cdot 10^5)\).

Salida

Una línea con la mínima cantidad de instrucciones.

Ejemplo 1

Entrada

ababcdcxx 2

Salida

3

Ejemplo 2

Entrada

aaabbcd 1

Salida

4

Ejemplo 3

Entrada

abcabca 3

Salida

1

Regional Latinoamericana 2022 del ICPC, problema L («Lazy Printing»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.