{"problem":{"name":"atcoder < S","description":{"content":"Given is a string $S$ consisting of lowercase English letters. Snuke can do the operation of swapping two **adjacent** characters in $S$. For example, if $S=$`agc`, one operation can change it to `gac","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc048_a"},"statements":[{"statement_type":"Markdown","content":"Given is a string $S$ consisting of lowercase English letters. Snuke can do the operation of swapping two **adjacent** characters in $S$. For example, if $S=$`agc`, one operation can change it to `gac` (by swapping `a` and `g`) or `acg` (by swapping `g` and `c`).\nSnuke wants to do this operation zero or more times so that `atcoder` $<S$ holds lexicographically.\nThe definition of the lexicographic relation $x< y$For strings $x$ and $y$, it is said that $x< y$ holds lexicographically if and only if one of the following conditions is satisfied:\n\n*   There exists an integer $i$ ($1 \\leq i \\leq \\mathrm{min}(|x|,|y|)$) such that the first $i-1$ characters of $x$ and those of $y$ are equal and the $i$\\-th character of $x$ is strictly smaller than that of $y$ in alphabetical order.\n*   $|x|< |y|$ holds, and the first $|x|$ characters of $y$ are equal to $x$.\n\nDetermine whether the objective is achievable. If it is achievable, find the minimum number of operations needed.\nSolve $T$ test cases in an input file.\n\n## Constraints\n\n*   $1 \\leq T \\leq 100$\n*   $1 \\leq |S| \\leq 1000$\n*   $S$ is a string consisting of lowercase English letters.\n\n## Input\n\nInput is given from Standard Input in the following format. The first line of input is as follows:\n\n$T$\n\nThen, $T$ test cases follow, each of which is in the following format:\n\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc048_a","tags":[],"sample_group":[["3\natcodeer\ncodeforces\naaa","1\n0\n-1\n\n*   The first test case: for example, swapping the last two characters makes $S=$`atcodere` $>$ `atcoder` hold.\n*   The second test case: before doing any operation, we already have $S=$`codeforces` $>$ `atcoder`.\n*   The third test case: no sequence of operations makes $S>$ `atcoder` hold."]],"created_at":"2026-03-03 11:01:14"}}