题目描述

对于一棵有根二叉树 $T$，小蓝定义这棵树中结点的权值 $W_T$ 如下： 空子树的权值为 0。 如果一个结点 $v$ 有左子树 $L$, 右子树 $R$，分别有 $C_L$ 和 $C_R$ 个结点，则 $W_v = 1 + 2W_L + 3W_R + C_L^2 C_R$。

树的权值定义为树的根结点的权值。 小蓝想知道，对于一棵有 $N$ 个结点的二叉树，树的权值最小可能是多 少？

输入描述

第一行包一个整数 $T$，表示测试数据的规模。

接下来 $T$ 行每行 $1$ 个整数 $N$。

输出描述

对每个输入输出一个整数表示答案。

2
40
2019

14796
2645702381

评测用例规模与约定：

对于所有评测用例，$1≤T≤10，1≤N≤3000$。