By keeping each queue in a sorted state, we can respond to a pop query at any time.

Two sorted queues \(A\) and \(B\) can be merged using \(|A|+|B|\) move operations. (While moving \(B\) to itself to rotate it by one full cycle, move elements of \(A\) at the appropriate timings.)

We can perform the operations according to the following rule.

• When the size of queue \(i\) becomes \(9^{i-1}\) or more, merge it into queue \(i+1\).

Since \(Q<9^4\), the size of queue \(4\) never becomes \(9^4\) or more. An upper bound on the total number of move operations can be estimated as follows.

• The total number of move operations used for merges from queue \(i\) to queue \(i+1\) is \((1+2+\ldots+9)9^i \times (Q/9^{i+1}) = 5Q\).
• That is, the total number of move operations is at most \(20Q\).