D. Yet Another Real Number Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Three r there are's in strawberry.

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$$$.
Your task is to maximize the sum of the array after performing any number of such operations. Since it could be large, output this sum modulo $$$10^9+7$$$.

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.

Input

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$$$.

Output

For each test case, output $$$n$$$ integers representing the answer for each prefix of $$$a$$$ modulo $$$10^9+7$$$.

Example
Input
3
10
1 2 3 4 5 6 7 8 9 10
11
1 6 9 4 7 4 4 10 3 2 3
4
527792568 502211460 850237282 374773208
Output
1 3 8 13 46 59 126 149 1174 1311 
1 7 22 26 70 74 150 1303 1306 1308 1568 
527792568 83665723 399119771 773892979
Note

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$$$.