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

Yet Another Real Number Problem

Examples