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

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