String rotations

Given a string $s$ of size $n$ , we define the $i$ -th rotation of $s$ (for $0 \le i < n$ ) as $s_i s_{i+1} \dots s_{n-1} s_0 \dots s_{i-2} s_{i-1} \enspace .$

Given two strings $s$ and $t$ , compute how many $i$ -th rotations of $s$ are equal to $t$ .

For instance, for $s =$ “abbabb” and $t =$ “babbab” the answer is 2, corresponding to $i = 2$ and $i = 5$ .

Input

Input consists of several cases, each one with two strings $s$ and $t$ with only lowercase letters. Assume $1 \le \vert s \vert = \vert t \vert \le 10^5$ . Every letter appears the same number of times in $s$ and in $t$ .

Output

For every case, print the number of $i$ -th rotations of $s$ that are equal to $t$ .

Problem information

Author: Salvador Roura

Generation: 2026-01-25T11:11:45.976Z