Define a block in a binary string (a string consisting of characters 0 and/or 1 ) as its continuous substring of characters of the same type that cannot be extended either to the left or to the right. For example, in the string 110001111 , there are three blocks: 11 (from the (1)-st character to the (2)-nd character); 000 (from the (3)-rd character to the (5)-th character); 1111 (from the (6)-th character to the (9)-th character). The substring from the (7)-th character to the (9)-th character 111 is not a block because it can be extended to the left. The substring from the (1)-st character to the (5)-th character 11000 is not a block because it contains characters of different types. We call a string beautiful if we can remove exactly one block from it so that the resulting string consists of an odd number of blocks. For example: the string 110001111 is beautiful because we can remove the block from the (3)-rd to the (5)-th character, resulting in the string 111111 , which consists of one block; the string 1010 is beautiful because we can remove the block from the (1)-st to the (1)-st character, resulting in the string 010 , which consists of three blocks; the string 0000 is not beautiful because the only way to remove a block from it will result in an empty string, which consists of (0) blocks. You are given an integer (n) and (m) constraints, the (i)-th of which is described by a pair of integers (l_i, r_i). We denote the substring of the string (s) from character (l) to character (r) inclusive as (sl:r), that is, (sl:r = s_l s_{l+1} \dots s_r). Your task is to count the number of binary strings (s) of length (n) meeting the following condition: for each (i) from (1) to (m), the string (sl_i:r_i) is beautiful. The first line contains one integer (t) ((1 \le t \le 10^4)) — the number of test case. The first line of each te