You can solve it o(1) just precalc answers fir all test by brute forse, than put it to array.
Proffit