You are given an array (b) of length (m). You can perform the following operation any number of times (possibly zero): Choose two distinct indices (i) and (j) where (\bf{1\le i < j\le m}) and (b_i) is even, divide (b_i) by (2) and multiply (b_j) by (2). Since this problem is too easy, you are given an array (a) of length (n) and need to solve the problem for each prefix of (a). In other words, denoting the maximum sum of (b) after performing any number of such operations as (f(b)), you need to output (f(a_1)), (f(a_1,a_2)), (\ldots), (f(a_1,a_2,\ldots,a_n)) modulo (10^9+7) respectively. The first line contains a single integer (t) ((1\le t\le 10^4)) — the number of test cases. The first line of each test case contains a single integer (n) ((1 \le n \le 2 \cdot 10^5)) — the length of (a). The second line contains (n) integers (a_1, a_2, \ldots, a_n) ((1 \le a_i \le 10^9)) — the starting values of array (a). It is guaranteed that the sum of (n) over all test cases will not exceed (2 \cdot 10^5). For each test case, output (n) integers representing the answer for each prefix of (a) modulo (10^9+7). For each prefix in the first example, a possible array after operations is: (1) and the sum is (1); (1, 2) and the sum is (3); (1, 1, 6) and the sum is (8); (1, 1, 3, 8) and the sum is (13); (1, 1, 3, 1, 40) and the sum is (46); (1, 1, 3, 1, 5, 48) and the sum is (59); (1, 1, 3, 1, 5, 3, 112) and the sum is (126); (1, 1, 3, 1, 5, 3, 7, 128) and the sum is (149); (1, 1, 3, 1, 5, 3, 7, 1, 1152) and the sum is (1174); (1, 1, 3, 1, 5, 3, 7, 1, 9, 1280) and the sum is (1311).