G. Max Binary Tree Width
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Determine the maximum possible width of any possible binary tree constructed with $$$n$$$ nodes.

- A binary tree is defined as any tree where all nodes have at most 2 children.

- The width of a tree is defined as the maximum number of nodes at any level of the tree. Null nodes do not contribute to the width of the tree.

Input

The first line of input will contain an integer $$$t$$$ ($$$1 \leq t \leq 2 \times 10^5$$$), indicating that there are $$$t$$$ test cases. The next $$$t$$$ lines will each contain an integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$), the input for each test case.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-6$$$ satisfy $$$1 \leq n \leq 10^5$$$.

Tests $$$7-20$$$ satisfy no additional constraints.

Output

Output one integer on a separate line per test case, the maximum possible width of any binary tree constructed with $$$n$$$ nodes.

Example
Input
3
4
10
17
Output
2
4
8
Note

Problem Idea: Mustela_Erminea

Problem Preparation: Mustela_Erminea

Occurrences: Novice G / Advanced B