设 $s = s_1s_2 \dots s_k$ 为一个长度为 $k$ 的字符串。对于任何 $0$ 到 $k-1$（含）之间的整数 $i$，我们定义 $s$ 的第 $i$ 次循环移位为字符串 $s_{i+1}s_{i+2} \dots s_k s_1 \dots s_i$。例如，“wellplayed”的第 $4$ 次循环移位是“playedwell”，而“metro”的第 $0$ 次循环移位是其自身。

定义函数 $f(s)$，对于长度为 $k$ 的字符串，其值为满足“$s$ 的第 $i$ 次循环移位在所有循环移位中字典序最小”的 $i$。如果有多个这样的 $i$，则 $f(s)$ 取其中最小的一个。例如，$f(\text{“acabbac”}) = 2$，而 $f(\text{“cabcab”}) = 1$。

定义函数 $g(s)$，对于长度为 $n$ 的字符串，其值为所有 $1 \le k \le n$ 的 $f(s_1s_2 \dots s_k) \cdot 8753^{k-1}$ 之和。

对于每个给定的字符串 $s$，求 $g(s)$ 对 $10^9 + 123$ 取模的结果。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。 接下来的 $t$ 行，每行包含一个由小写英文字母组成的非空字符串。 所有输入字符串的总长度不超过 $10^6$。

输出格式

对于每个输入的字符串 $s$，输出一行，包含一个整数，即 $g(s)$ 对 $10^9 + 123$ 取模的结果。

样例

输入 1

2
aab
acabbac

输出 1

0
38098220

说明

在第一个样例测试用例中，$f(\text{“a”}) = 0$，$f(\text{“aa”}) = 0$，且 $f(\text{“aab”}) = 0$。因此，$g(\text{“aab”}) = 0$。

以下是第二个样例测试用例中 $f(s_1s_2 \dots s_k)$ 的值列表：

• $f(\text{“a”}) = 0$；
• $f(\text{“ac”}) = 0$；
• $f(\text{“aca”}) = 2$；
• $f(\text{“acab”}) = 2$；
• $f(\text{“acabb”}) = 2$；
• $f(\text{“acabba”}) = 5$；
• $f(\text{“acabbac”}) = 2$。

因此，$g(\text{“acabbac”}) = 2 \cdot 8753^2 + 2 \cdot 8753^3 + 2 \cdot 8753^4 + 5 \cdot 8753^5 + 2 \cdot 8753^6 = 899695598935764095704157$，其对 $10^9 + 123$ 取模的结果为 $38098220$。