Claire loves drawing lines. She receives a sheet of paper with an (n \times n) grid and begins drawing "lines" on it. Well—the concept of a "line" here is not what we usually think of. Claire refers each line to be a set of consecutive vertical grid cells. When she draws a line, these cells are all covered with black ink. Initially, all the cells are white, and drawing lines turns some of them black. After drawing a few lines, Claire wonders: how many ways she can color an additional white cell black so that the remaining white cells do not form a single connected component. Two cells are directly connected if they share an edge. Two cells (x) and (y) are indirectly connected if there exists a sequence of cells (c_0, c_1, \ldots, c_k) with (k > 1) such that (c_0 = x), (c_k = y), and for every (i \in \{1, 2, \ldots, k\}) the cells (c_i) and (c_{i-1}) are directly connected. A set of cells forms a single connected component if each pair of cells in the set is either directly or indirectly connected. The grid has (n) rows and (n) columns, both indexed from (1) to (n). Claire will draw (q) lines. The (i)-th line is drawn in the (y_i)-th column, from the (s_i)-th row to the (f_i)-th row, where (s_i \leq f_i) for each (i \in \{1, 2, \ldots, q\}). Note that the cells that are passed by at least one of the (q) lines are colored black. The following figure shows an example of a (20\times 20) grid with (q=67) lines. The grid cells marked with red star symbols refer to the cells such that, if Claire colors that cell black, all white cells no longer form a single connected component. You may assume that, after drawing the (q) lines, the remaining white cells form a single connected component with at least three white cells. The first line contains exactly one integer (t), indicating the number of test cases. For each test case, it begins with a line containing exact