It seems to be sufficient to process each test case in a constant time.

We will describe an example of consideration process below.

• We want to find the answer \(ans\)
• It seems to be complicated to find the \(ans\): the number of ways to place red and blue squares so that they do not overlap, so let us subtract the number of ways to place red and blue squares so that they do overlap (which we will denote \(X_1\)) from the total number of placing squares \(ans = (N-A+1)^2(N-B+1)^2 - X_1\)
• When \(X_1\): the red and blue squares overlap, both of the following two conditions must hold: “the range of \(x\) coordinates of the red square and the range of \(x\) coordinates of the blue square overlap” and “the range of \(y\) coordinates of the red square and the range of \(y\) coordinates of the blue square overlap.” By symmetry those two value are the same (which we will denote \(X_2\)), so \(X_1 = X_2^2\)
• \(X_2\): the number of placing a segment of length \(A\) and a segment of length \(B\) in a segment of length \(N\) such that the first two segments overlap. It seems it can be found by subtracting the number of placing the segments such that they do not overlap (which we will denote \(X_3\)) from the total number of placing them; that is, \(X_2 = (N-A+1)(N-B+1) - X_3\)
• \(X_3\): by symmetry, we can split the cases by whether red or blue segment is in the left. Let \(X_4\) be the number of cases where the red one is in the left, then \(X_3 = 2X_4\)
• \(X_4\): each case will be like (blank)(red)(blank)(blue)(blank) and the number of empty cells is \(N-A-B\), so if \(N-A-B < 0\), \(X_4 = 0\); if \(N-A-B ≥ 0\), \(X_4 = (N-A-B+2)(N-A-B+1)/2\).
• Now you can code them bottom-up