概要

マルチテストであることを活かした問題です．
基本的には全探索ですが，工夫して高速化しましょう．

問題原案：uni_kakurenbo

解説

愚直解を考える

$N \leq 10$ であることに注目しましょう．

すべての長さが $10$ 以下の PDCA-String を頂点とし，題中の操作を $($操作前の文字列$) \to ($操作後の文字列$)$ の有向辺で表現したグラフ $G$ を考えます．

$S$ を PDCA-Cyclic な文字列にするための操作回数の最小値は，$S$ から任意の PDCA-Cyclic な文字列までの最短距離(通る辺の本数の最小値)に一致します．(到達できなかった場合が -1．)

$G$ の頂点のうち長さが $N$ であるものは $4^N$ 個，各頂点から出る辺は $\Theta(N)$ 本ですから，BFS 等を用いることで $O(N^2 4^N)$ 時間などで実装できます．

しかし，$\Phi \leq 10^5$ であるのでテストケース毎に $\Omega(N^2 4^N)$ 時間で求めていては実行時間制限に間に合わせるのは絶望的です．

この解法をベースに高速化を図りましょう．

始終点の入れ替えと前計算

適当な $2$ 頂点を $s, t$ について，$s \to t$ の最短距離と $t \to s$ の最短距離とは等しいです．

$M = \max N$ とします．

長さ $n \scriptsize \; (1 \leq n)$ の PDCA-Cyclic な文字列は，$n$ に依らず $4$ 通りしかないため，全体で見ても PDCA-Cyclic な文字列は $4M \leq 40$ 通りしかありません．$\scriptsize (\because M \leq 10)$
ゆえに，$G$ 上の探索においては，様々な非 PDCA-Cyclic な文字列から $4M$ 個の PDCA-Cyclic な文字列のうちいずれかへの最短経路を求めていることになります．

したがって，PDCA-Cyclic な文字列への最短距離をケースごとに求めるより，ある PDCA-Cyclic な文字列から辺を逆向きに辿ることで到達できる PDCA-String を列挙する方が効率的です．

これならば $\Phi$ 個のテストケースに答える前に高々 $4M$ 回の BFS を行えばすべての入力について答えが求まります．

しかし，依然として BFS 一回につき worst $\Omega (M^2 4^M)$ 時間程度を要すので，これでも実行時間制限に間に合わせることは厳しそうです．

多始点 BFS

同じグラフ上での BFS を $4M$ 回行う代わりに，一回の BFS で $4M$ 個すべての頂点を始点として探索を行うことができます．
これでも一回当たりの BFS の時間計算量のオーダーは悪化せず，(辞書などで管理された)前計算によって得られた答えを検索するコストも含めて，一つのテストあたり worst $O((M^24^M + \Phi) M)$ 時間や expected $O(M^24^M + \Phi)$ 時間などで答えることができます．

計算量のより正確な評価 (軽い定数倍)

このとき $M = 10$ において $M^24^M \simeq 10^8$ であり，実行時間制限に間に合うかどうかはとても微妙に思えます．

しかし，$G$ のうち BFS によって実際に探索される頂点は $4M$ 個の PDCA-Cyclic な頂点から有限回の(逆)操作を経由して到達できるものに限られます．

この個数をより正確に評価してみましょう．
場合の数などを用いて数学的に考えても求まりますが，実際に多始点 BFS を実装し，最終的に到達した頂点の個数を数えれば答えが分かります．($137100$ 頂点です．)

また，(愚直解を考える の項での時間計算量の評価でもそのように考えていますが，) $G$ の連結成分は，長さの等しい PDCA-String の集合を頂点としてなされているので，実際のところ $4M$ 回の BFS を回したとしても，そのたびに $Θ(4^M)$ 個の頂点がすべて訪れられるわけではありませんし，なおかつ短い PDCA-String ほどその頂点から出る辺の本数も少ないです．

ここから全体の時間計算量の(より精度の高い)評価に戻ってもよいですが，そもそも入力に依存しない前計算が実行時間制限に余裕を持って終了することが確認できているならば，それをそのまま用いて実装したものを提出しても問題はないだろうと考えられます．

なお PDCA-String を $4$ 進数や $5$ 進数などとみなして管理することで worst $O(M 4^M + \Phi)$ 時間を達成できますが，多くの場合でここまでの高速化は不要でしょう．(といいながら次項の おまけ ではそのように実装しています．)

おまけ：コンパイル時前計算

PDCA-String に適当な変換を施して数値として扱えるようにすることでコンパイル時に探索を行い，更なる実行時間の短縮を図ることができる，可能性があります．
キューの代替法などは少々工夫する必要がありますが，これは少し頑張るとできます．(詳しくは実装例を参照してください．)

なお C++20 では std::string や std::vector が constexpr に対応するため，より簡単に実現できるようになります．

(-fconstexpr-ops-limit や -fconstexpr-loop-limit の制約によってはコンパイルできないかもしれません．MojaCoder ではできませんでした．私の手元環境でもメモリ不足により無理でした．)

解説：uni_kakurenbo

実装例