暴力肯定不行，尝试简单讨论一下。
-
如果 \(q > \sqrt n\)，那么 \(p^2 < \sqrt n\)，\(p < \sqrt[4]{n}\)，枚举 p 就行。
-
如果 \(p^2 > \sqrt n\)，那么 \(p < \sqrt n\)，因为 \(q < \sqrt n\)，所以 \(\min(p,q) \le \sqrt[3]{n}\)，也可以直接枚举。
综上，两种情况分别枚举就行了，美滋滋~。
复杂度 \(O(T\sqrt[3]{n})\)。
简单诈骗题。
\(\min(K,10^6)\) 保证了复杂度，所以直接 dfs 就行了。
复杂度 \(O(10^6+m)\)。
字符串哈希。
稍微转化一下题意，就可以发现字符串 \(s=AB'A'B\)，其中 \(A'\) 为 \(A\) 的反串，\(B'\) 同理。
所以我们枚举 A，哈希 \(O(1)\) 判断是否满足要求。
注意卡自然溢出。
复杂度 \(O(|s|)\)。