Consider the value \(L = \text{lcm}(1,2,3,...,8) = 2^3 \cdot3\cdot5\cdot7 = 840\). First solve the problem naively for \(q \in \{0,1,2,...,L-1\}\), let \(r(q)\) denote the answer for \(q\).

Note that \(r(q + L) = r(q) + L\) for all integers \(q\). This is because the time “wasted” at each bus stop only depends on \(s \text{ mod } P_i\) where \(s\) is the time of arrival at the bus stop, which depends only on the time used on all previous bus stops, and congruence \(\text{mod } L\) implies congruence \(\text{mod } P_i\) for all \(i\).

Therefore we can solve the given queries via \(r(q) = r(q \text{ mod } L) + \lfloor q / L \rfloor \cdot L\), with the first term being one of the values we had precomputed.

The problem has been solved in time \(O(LN+Q)\) and space \(O(N + L)\).