问题2394--玩《三国志·如鸢》玩的!!

2394: 玩《三国志·如鸢》玩的!!

[命题人 : ]
时间限制 : 3 sec  内存限制 : 128 MB

提交

题目描述

《三国志·如鸢》登场!为了让更多的玩家领略到这款精心打造的游戏,游戏开发公司倾心制作,然而知晓的人却寥寥无几。现如今,我们的目标是让《三国志·如鸢》闪耀于众,让每一位游戏爱好者都能品味到其中的乐趣!但是游戏开发公司把经费都砸在了游戏开发上面,支付不起昂贵的广告费,于是提出帮广告公司解决问题来支付一些广告费用。正好广告公司有一个遗留很久的问题,还没等广告公司把问题说出来,游戏公司就信誓旦旦的说他们一定能解决这个问题。

于是广告公司拿出一张泛黄的纸,上面写着: 给定一张n个点的无向完全图,其中两点之间的路径边权为两点编号的按位与(编号为(1,2,......,n),即w(u, v) = u & v(1≤u,v≤n ),求该图最小生成树的边权和。

游戏公司的人拿到这张纸之后,罚站了30分钟,很显然他们也解决不了这个问题,于是他们向你寻求帮助,作为回报,他们提出在你大学毕业之后就会录用你到他们公司工作。

输入

本题包含多组数据:
第一行包含一个整数T(1≤T≤1e3),代表测试用例的组数 对于每组数据:
第一行输入一个正整数n(2≤n≤1e9),代表该完全图的节点个数。

输出

对于每组数据:
输出一行一个整数,代表该完全图最小生成树的边权和。

样例输入 Copy

1
3

样例输出 Copy

1

来源/分类