Binary Products#2947
You are given a sequence consisting of ones. Consider all possible ways to insert one or more multiplication signs between the ones, so that the resulting expression is valid (multiplication signs cannot appear consecutively, and they cannot appear at the beginning or end of the sequence). For example, for n = 4, there are ways: 1\times111, 11\times11, 111\times1, 1\times1\times11, 1\times11\times1, 11\times1\times1, and 1\times1\times1\times1. Next, compute the sum of the products of these expressions, interpreting the numbers as written in binary: 1_2\times111_2 + 11_2\times11_2 + 111_2\times1_2 + 1_2\times1_2\times11_2 + 1_2\times11_2\times1_2 + 11_2\times1_2\times1_2 + 1_2\times1_2\times1_2\times1_2 = 33.
You need to compute this sum for any .
The first line contains (1 \le T \le 1000) — the number of test cases. The following lines each contain a single integer (2 \le n \le 10^9).
For each in the input, output the required sum modulo .
Example 1