Problem title
Difficulty
Avg time to solve

Prim's MST
Moderate
15 mins
Row with Maximum 1's
Easy
10 mins
Is Graph Tree?
Easy
15 mins
Segregate Even And Odd Nodes In a Linked List
Easy
15 mins
Max Product Subset
Moderate
15 mins
Arranging Array
Easy
15 mins
Build Min Heap
Moderate
30 mins
Word Rectangle
Hard
15 mins
Ninja’s Service Center
Moderate
30 mins
Water
Easy
15 mins 8

# Count Set Bits

Difficulty: HARD
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

#### Since the count of ‘1’ can be huge, you are required to return it modulo 1e9+7.

##### Note:
``````Do not print anything, just return the number of set bits in the binary representation of all integers between 1 and ‘N’.
``````
##### Input Format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases to run.
Then the next ‘T’ lines represent the ‘T’ test cases.

The first line of each test case contains a single integer ‘N’.
``````
##### Output Format
``````For each test case, return an integer that is equal to the count of set bits in all integers from 1 to n modulo 1e9+7.

Output for each test case will be printed in a new line.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 10^9

Time limit: 1 second
``````
##### Sample Input 1:
``````2
5
3
``````
##### Sample Output 1:
``````7
4
``````
##### Explanation For Sample Input 1 :
``````In the first test case,

DECIMAL    BINARY      SET BIT COUNT
1            01                  1
2            10                  1
3            11                  2
4            100                 1
5            101                 2
1 + 1 + 2 + 1 + 2 = 7
Answer = 7 % 1000000007 = 7

In the second test case,

DECIMAL    BINARY      SET BIT COUNT
1            01                  1
2            10                  1
3            11                  2
1 + 1 + 2 = 4
Answer = 4 % 1000000007 = 4
``````
##### Sample Input 2:
``````2
6
10
``````
##### Sample Output 2:
``````9
17
``````   Console