Comments
On XbalanquePlease make more contests, 21 month(s) ago
+19

I think it should be at least 7 or 8.

You can use AC-automaton to do this.Firstly,take the inquiry offline,record the first appearing time for all s and build an AC-automaton for them.Process inquiries in time order,then you can use the fail tree and some data structures to solve it.