순환 시프트

길이가 $k$인 문자열을 $s = s_1 s_2 \ldots s_k$라고 하자. 0 이상 $k-1$ 이하의 임의의 정수 $i$에 대해, $s$의 $i$번째 순환 시프트는 $s_{i+1}s_{i+2} \ldots s_k s_1 \ldots s_i$이다. 예를 들어 wellplayed의 4번째 순환 시프트는 playedwell이고, metro의 0번째 순환 시프트는 metro 자체이다.

길이가 $k$인 문자열에 대해 $f(s)$는 $s$의 $i$번째 순환 시프트가 모든 순환 시프트 중 사전순으로 가장 작게 되는 $i$이다. 그런 $i$가 여러 개이면 그중 가장 작은 값을 $f(s)$로 한다. 예를 들어 f(acabbac) = 2, f(cabcab) = 1이다.

길이가 $n$인 문자열에 대해 $g(s)$는 $k$를 1부터 $n$까지 바꿔가며 $f(s_1 s_2 \ldots s_k) \cdot 8753^{k-1}$을 모두 더한 값이다. 주어진 각 문자열 $s$에 대해 $g(s)$를 $10^9 + 123$으로 나눈 나머지를 구하라.

첫 줄에 정수 $t$ ($1 \le t \le 10^4$)가 주어진다. 이어서 $t$개의 줄에 각각 비어 있지 않은 영소문자 문자열이 한 줄씩 주어진다. 입력 문자열들의 길이 합은 $10^6$을 넘지 않는다.

각 입력 문자열에 대해 입력 순서대로 $g(s)$를 $10^9 + 123$으로 나눈 나머지를 한 줄에 하나씩 출력한다.