There are very long classes in the T-Generation. In one day, you need to have time to analyze the training and thematic contests, give a lecture with new material, and, if possible, also hold a mini-seminar. Therefore, there is a break where students can go to drink coffee and chat with each other. There are a total of (n+2) coffee machines located in sequentially arranged rooms along a long corridor. The coffee machines are numbered from (0) to (n+1), and immediately after the break starts, there are (a_i) students gathered around the (i)-th coffee machine. The students are talking too loudly among themselves, and the teachers need to make a very important announcement. Therefore, they want to gather the maximum number of students around some single coffee machine. The teachers are too lazy to run around the corridors and gather the students, so they came up with a more sophisticated way to manipulate them: At any moment, the teachers can choose room (i) ((1 \le i \le n)) and turn off the lights there; If there were (x) students in that room, then after turning off the lights, (\lfloor \frac12 x \rfloor) students will go to room ((i-1)), and (\lfloor \frac12 x \rfloor) other students will go to room ((i+1)). If (x) was odd, then one student remains in the same room. After that, the lights in room (i) are turned back on. The teachers have not yet decided where they will gather the students, so for each (i) from (1) to (n), you should determine what is the maximum number of students that can be gathered around the (i)-th coffee machine. The teachers can turn off the lights in any rooms at their discretion, in any order, possibly turning off the lights in the same room multiple times. Note that the values of (a_0) and (a_{n+1}) do not affect the answer to the problem, so their values will not be given to you. The first line contains a single integer (t) ($$$1 \le t \le 10\,00