题目描述
这是这道题目的Hard版本，与Easy版本不同的是$n$的范围。
给定一个正整数$n$，需要你求出$ {\textstyle \sum_{i=0}^{2^{n} }} f\left ( i \right ) $
$f\left ( x \right ) $定义为$x$转化为二进制后1的数量，例如$10=\left ( 1010 \right ) _{2} ,7=\left ( 111 \right ) _{2} $，那么$f\left ( 10 \right ) = 2, f\left ( 7 \right ) =3$。
输入
第一行一个整数$T$，表示有$T$组数据。
接下来$T$行，每行一个整数$n$。
数据范围：$1\le n\le 31$，$1\le T\le 100$
输出
输出一个整数，表示$ {\textstyle \sum_{i=0}^{2^{n} }} f\left ( i \right ) $
提示
当$n=3$时，有$000,001,010,011,100,101,110,111,1000$，所以一共有13个1.
当$n=2$时，有$00,01,10,11,100$，所以一共有5个1.