给你一个由小写英文字母组成的字符串 $S$。 Snuke 可以交换 $S$ 中相邻的 $2$ 个字符。 例如，如果 $S =$agc，那么在一次操作中，$S$ 变为 gac（交换 a 和 g）或 acg（g 和 c 交换） .

Snuke 想要重复此操作 $0$ 次或若干次，使得 atcoder 的字典序小于 $S$。

判断目标是否可以实现，若能则求出需要的最少操作次数。

每个测试点包含 $T$ 组数据。

【提示】

数据千万条，清空第一条。多测不清空，爆零两行泪。