The key is in your dp state to not just hold the color of your current segment, but of the current segment and previous segment.

This question can be solved easily using dp with states 1. index , colour of last segment, colour of last to last segment. And for each state you will need to run a loop from 1 to m too .

So eventually adding this to test cases will lead to a O(T*N*M*M*M) solution ,but here we notice that the test cases aren't actually till 2500, since we know that the values of m ranges from 1 to 50.

So if we precompute for all m from 1 to 50, we solve the test case issue.

Here is my working code . Although I am not sure about the exact time complexity due to the coprime thing.