P16251 [Lanqiao Cup 2026 NOI Qualifier Graduate Group] Ground State Collapse

A quantum chain is formed by connecting $N$ nodes in order. The nodes are numbered from the front end to the back end as $1 \sim N$. The initial energy level of the $i$-th node is a positive integer $A_i$. Two control models, L and Q, play a game on this chain. Both use optimal strategies and take turns operating, with L moving first. Each time it is a model’s turn, it must perform one “downgrade intervention” on the current back-end node of the quantum chain (that is, the last node of the current sequence), following these rules: - Let the current energy level of the back-end node be $B$. - Its energy level must be reset to an integer $x$ such that $0 \leq x < B$. - If after resetting, the node’s energy level becomes $0$, then the node is immediately stripped from the chain. At this time, its previous node (if any) becomes the new back-end node. - If after resetting, the node’s energy level is greater than $0$, then the node remains at the back end of the chain, waiting for later operations to further downgrade it. The game continues until the quantum chain is completely stripped (that is, all nodes are removed). When it is a model’s turn to operate, if there are no nodes left on the chain, then that model is judged to lose because it cannot make a move, and the other side wins. Please determine who will win in the end when both sides play optimally.

The first line contains a positive integer $T$, which denotes the number of testdata sets. Then $T$ testdata sets follow. For each testdata set: - The first line contains a positive integer $N$, which denotes the total number of nodes in the quantum chain for this game. - The second line contains $N$ positive integers $A_1, A_2, \ldots, A_N$, representing the initial energy levels of the nodes from the front end to the back end. Adjacent values are separated by a single space.

For each testdata set, output one line with a single string. If control model L can win in the end, output `L`; otherwise, if model Q wins, output `Q`.

### Constraints and Notes For $30\%$ of the testdata, $1 \leq T \leq 100$, $1 \leq N \leq 10^3$, $1 \leq A_i \leq 10^3$, and the sum of $N$ over all testdata does not exceed $5 \times 10^3$. For all testdata, $1 \leq T \leq 10^4$, $1 \leq N \leq 10^5$, $1 \leq A_i \leq 10^9$, and the sum of $N$ over all testdata does not exceed $2 \times 10^5$. Translated by ChatGPT 5