Let there be a set that contains distinct positive integers. To expand the set to contain as many integers as possible, Eri can choose two integers (x\neq y) from the set such that their average (\frac{x+y}2) is still a positive integer and isn't contained in the set, and add it to the set. The integers (x) and (y) remain in the set. Let's call the set of integers consecutive if, after the elements are sorted, the difference between any pair of adjacent elements is (1). For example, sets (\{2\}), (\{2, 5, 4, 3\}), (\{5, 6, 8, 7\}) are consecutive, while (\{2, 4, 5, 6\}), (\{9, 7\}) are not. Eri likes consecutive sets. Suppose there is an array (b), then Eri puts all elements in (b) into the set. If after a finite number of operations described above, the set can become consecutive, the array (b) will be called brilliant . Note that if the same integer appears in the array multiple times, we only put it into the set once , as a set always contains distinct positive integers. Eri has an array (a) of (n) positive integers. Please help him to count the number of pairs of integers ((l,r)) such that (1 \leq l \leq r \leq n) and the subarray (a_l, a_{l+1}, \ldots, a_r) is brilliant. Each test consists of multiple test cases. The first line contains a single integer (t) ((1 \leq t \leq 10^4)) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer (n) ((1 \leq n \leq 4 \cdot 10^5)) — length of the array (a). The second line of each test case contains (n) integers (a_1, a_2, \ldots a_n) ((1 \leq a_i \leq 10^9)) — the elements of the array (a). It is guaranteed that the sum of (n) over all test cases doesn't exceed (4 \cdot 10^5). For each test case, output a single integer — the number of brilliant subarrays. In the first test case, the array (a = 2, 2) has (3) subarra