The answer is $n = \boxed{101}.$ To see that $n =101$ works, simply take color blue the top row of a $101 \times 101$ square. Call a row fallow if there are no blue squares in that row, and similarly for columns. Lemma 1. For a blue square and its non-blue neighbor, there exists a way to cut the table into rectangles which partitions these two squares into the same rectangle. Proof. Suppose WLOG that they are in the same row (else rotate the board $90$ degrees). First, we will partition the non-fallow rows into $1 \times k$ rectangles, each containing exactly one blue square. Make sure that the two squares described above are partitioned into the same rectangle, which is easy to do. Now, we will collapse the fallow rows into the existing rectangles. For instance, just put every square in a fallow row in the first rectangle below it (which intersects its column), and the first one above it if there are non below it. The lemma is proven. $\blacksquare$ Corollary. The set of blue squares in any row is contiguous. Proof. If not, then we could partition that row into $1 \times k$'s in more than one way, and then proceeding in the way described in the proof of Lemma 1 gives that there are at least two possible ways to partition the grid, contradiction. $\blacksquare$ Clearly, a similar statement holds for columns. Lemma 2. Any non-blue square $s$ cannot have two blue neighbors. Proof. By Corollary above, we only need to prove it when the two blue neighbors are not in the same row or column. Let $n_1$ be the blue neighbor which is in the same row and $n_2$ be the blue neighbor in the same column. Use the algorithm described in Lemma 1 to get a partition with $n_1, s$ in the same rectangle but not $n_2$, and then one with $n_2, s$ in the same rectangle but not $n_1.$ $\blacksquare$ Lemma 3. If $a, b$ are blue squares which aren't in the same row or the same column, then the rectangle with $a, b$ as opposite corners is entirely blue. Proof. WLOG assume that $a$ is lower than $b$ and to the left of $b$. Consider the path $a s_1 s_2 \cdots s_k b$ which first goes up and then to the right, moving one step each time. Let $s_t$ be the turning point, i.e. $s_t$ is above $s_{t-1}$ and to the left of $s_{t+1}.$ Observe that if any $s_i$ is not blue, then $s_t$ is not blue by corollary. Suppose that $s_t$ was not blue. Let $0 \le i < t$ be the largest $i$ with $s_i$ blue, where $s_0 = a$ by convention. Let $t < j \le k+1$ be the smallest $j$ with $s_j$ blue, where $s_{k+1} = b$ by convention. Then, apply the algorithm in the lemma to get a partitioning where $s_i, s_t$ are in the same rectangle but not $s_j$, and another where $s_j, s_t$ are in the same rectangle but not $s_i$. These give a contradiction, and so therefore all the $s_i$'s are blue. Now, using Lemma 2, we can prove that the entire rectangle is blue. $\blacksquare$ Lemma $3$ is enough to imply that the set of blue squares forms a rectangle (look at the squares with highest/lowest $x-$/$y-$coordinate, and apply the lemma on pairs of those). This means that the set of blue squares must be a $1 \times 101$ rectangle, which implies $n \ge 101,$ as desired. Hence, the desired minimum value of $n$ is $\boxed{101}.$ $\square$