The last contest held on Johnny’s favorite competitive programming platform has been received rather positively. However, Johnny’s rating has dropped again! He thinks that the presented tasks are lovely, but don’t show the truth about competitors’ skills.

The boy is now looking at the ratings of consecutive participants written in a binary system. He thinks that the more such ratings differ, the more unfair is that such people are next to each other. He defines the difference between two numbers as the number of bit positions, where one number has zero, and another has one (we suppose that numbers are padded with leading zeros to the same length). For example, the difference of 5=1012 and 14=11102 equals to 3, since 0101 and 1110 differ in 3 positions. Johnny defines the unfairness of the contest as the sum of such differences counted for neighboring participants.

Johnny has just sent you the rating sequence and wants you to find the unfairness of the competition. You have noticed that you’ve got a sequence of consecutive integers from 0 to n. That’s strange, but the boy stubbornly says that everything is right. So help him and find the desired unfairness for received numbers.

Input
The input consists of multiple test cases. The first line contains one integer t (1≤t≤10000) — the number of test cases. The following t lines contain a description of test cases.

The first and only line in each test case contains a single integer n (1≤n≤1018).

Output
Output t lines. For each test case, you should output a single line with one integer — the unfairness of the contest if the rating sequence equals to 0, 1, …, n?1, n.

Example
Input
5
5
7
11
1
2000000000000
Output
8
11
19
1
3999999999987
Note
For n=5 we calculate unfairness of the following sequence (numbers from 0 to 5 written in binary with extra leading zeroes, so they all have the same length):

000
001
010
011
100
101
The differences are equal to 1, 2, 1, 3, 1 respectively, so unfairness is equal to 1+2+1+3+1=8.
思路：我們可以找找規(guī)律。
拿樣例來說：
右數(shù)第一位，一共貢獻了5個，也就是n/(2^0)
右數(shù)第二位，一共貢獻了2個，也就是n/(2^1)
右數(shù)第三位，一共貢獻了1個，也就是n/(2^2)
規(guī)律就很明顯了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;ll n;int main() {int t;scanf("%d",&t);while(t--){scanf("%lld",&n);ll ans=0;ll nn=n;ll i=1;while(nn){ans+=n/i;i<<=1ll;nn>>=1ll;}cout<<ans<<endl;}return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Johnny and Another Rating Drop CodeForces - 1362C（规律）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。