P16790 [Lanqiao Cup 2026 National A] Magic Prefix

XiaoLan and XiaoQiao jointly maintain a large dictionary. To free up storage space, they decide to delete unnecessary word prefixes through a “prefix pruning” magic game. The dictionary contains $N$ words consisting of lowercase English letters. Define the valid prefix set of the dictionary as the set of all non-empty prefixes of all words in the dictionary. Each identical prefix is kept only once. For example, if the dictionary contains only the words `cat` and `car`, then the valid prefix set is `c`, `ca`, `cat`, `car`. The rules of the game are: 1. XiaoLan and XiaoQiao take turns, with XiaoLan going first. 2. On each turn, the current player must choose a non-empty prefix $P$ from the current valid prefix set. 3. After choosing $P$, all strings in the current set that have $P$ as a prefix will be deleted, including $P$ itself. For example, if the current valid prefix set is $\{$"a", "ap", "app", "b", "ba"$\}$ and the player chooses "ap", then "ap" and "app" will both be deleted, and the set becomes $\{$"a", "b", "ba"$\}$. 4. When it is a player’s turn, if the valid prefix set is empty, then that player loses the game. Both players will use optimal strategies. Given the initial dictionary, determine who will win in the end.

The first line contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $N$, indicating the number of words in the dictionary. The next $N$ lines each contain a string consisting of lowercase English letters, representing a word.

For each test case, output one line. If XiaoLan is guaranteed to win, output XiaoLan; otherwise output XiaoQiao.

### Sample Explanation In the first sample, the valid prefix set is `a`, `ab`, `c`, `cd`. The two branch structures are exactly the same. No matter which prefix XiaoLan chooses on one branch, XiaoQiao can make a symmetric move on the other branch, so XiaoQiao is guaranteed to win. In the second sample, the valid prefix set is `c`, `ca`, `cat`, `car`. XiaoLan chooses `c` on the first move, which deletes the entire set and leaves XiaoQiao with no moves, so XiaoLan is guaranteed to win. ### Constraints For $30\%$ of the test cases, the total length of all strings in a single test case does not exceed $20$. For all test cases, $1 \le T \le 10$, $1 \le N \le 10^5$. The sum of string lengths over all test cases in a single input file does not exceed $10^6$. All strings contain only lowercase English letters. Translated by ChatGPT 5