Cyclic Shifts

Let $s = s_1 s_2 \ldots s_k$ be a string of length $k$. For any integer $i$ between 0 and $k-1$, inclusive, the $i$-th cyclic shift of $s$ is the string $s_{i+1}s_{i+2} \ldots s_k s_1 \ldots s_i$. For example, the 4-th cyclic shift of wellplayed is playedwell, and the 0-th cyclic shift of metro is metro itself.

For a string of length $k$, $f(s)$ is the index $i$ such that the $i$-th cyclic shift of $s$ is the lexicographically smallest among all its cyclic shifts. If several such $i$ exist, $f(s)$ is the smallest of them. For example, f(acabbac) = 2 and f(cabcab) = 1.

For a string of length $n$, $g(s)$ is the sum of $f(s_1 s_2 \ldots s_k) \cdot 8753^{k-1}$ over all $k$ from 1 to $n$, inclusive. For each given string $s$, find the value of $g(s)$ modulo $10^9 + 123$.

The first line contains a single integer $t$ ($1 \le t \le 10^4$), the number of test cases. Each of the next $t$ lines contains a non-empty string of lowercase English letters. The total length of the input strings does not exceed $10^6$.

For each input string, in input order, output a single integer: $g(s)$ modulo $10^9 + 123$.