Akash and Function

 Akash has his maths test tomorrow. He secretly found out one of the questions from the test. As the test is online, he wants to write a code that solves the question. However, he is not good at coding and thus, wants Chef to help him with that.

Chef is given a function F(X)$F(X)$ such that the condition:

• F(X)=F(2⋅X)$F(X)=F(2\cdot X)$
  holds true for all X$X$, where X$X$ is a positive integer.

For a given positive integer N$N$, find the maximum number of distinct elements in the array [F(1),F(2),F(3),…,F(N)]$[F(1),F(2),F(3),\dots ,F(N)]$.

Input Format

• First line will contain T$T$ - the number of test cases. Then the test cases follow.
• Each test case contains a single line of input, one integer N$N$.

Output Format

For each test case, output in a single line, the maximum number of distinct elements in the array [F(1),F(2),F(3),…,F(N)]$[F(1),F(2),F(3),\dots ,F(N)]$.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤N≤109$1\le N\le {10}^9$

Subtasks

• Subtask 1 (30 points): 1≤N≤1000$1\le N\le 1000$
• Subtask 2 (70 points): Original Constraints.

Sample Input 1 

2
2
5

Sample Output 1 

1
3

Explanation

Test case 1$1$: Let X=1$X=1$. Thus, 2=2⋅1=2⋅X$2=2\cdot 1=2\cdot X$. Therefore, F(1)=F(2)$F(1)=F(2)$. So, in the array [F(1),F(2)]$[F(1),F(2)]$, there is only 1$1$ distinct element.

Test case 2$2$: Here, we can take X=1$X=1$. Thus F(1)=F(2)$F(1)=F(2)$. Similarly, if we take X=2$X=2$, F(2)=F(4)$F(2)=F(4)$. This means that F(1)=F(2)=F(4)$F(1)=F(2)=F(4)$.
However, it can be possible that the values F(1),F(3),$F(1),F(3),$ and F(5)$F(5)$ are distinct. Hence, the maximum number of distinct elements in the array [F(1),F(2),F(3),F(4),F(5)]$[F(1),F(2),F(3),F(4),F(5)]$ is 3$3$.

• Tweet
• Share
• Share
• Share
• Share

Related Post