题目描述
给定 T 个数 n1, n2, · · · , nT，对每个 ni 请求出有多少组 a, b, c 满足：
1. 1 ≤ a, b, c ≤ ni；
2. a ⊕ b ⊕ c = 0，其中 ⊕ 表示二进制按位异或；
3. 长度为 a, b, c 的三条边能组成一个三角形。
1. 1 ≤ a, b, c ≤ ni；
2. a ⊕ b ⊕ c = 0，其中 ⊕ 表示二进制按位异或；
3. 长度为 a, b, c 的三条边能组成一个三角形。
输入格式
输入的第一行包含一个整数 T。
接下来 T 行每行一个整数，分别表示 n1, n2, · · · , nT。
接下来 T 行每行一个整数，分别表示 n1, n2, · · · , nT。
输出格式
输出 T 行，每行包含一个整数，表示对应的答案。
样例输入
2 6 114514
样例输出
6 11223848130
提示
【评测用例规模与约定】
对于 10% 的评测用例，T = 1, 1 ≤ ni ≤ 200；
对于 20% 的评测用例，T = 1, 1 ≤ ni ≤ 2000；
对于 50% 的评测用例，T = 1, 1 ≤ ni ≤ 220；
对于 60% 的评测用例，1 ≤ T ≤ 100000, 1 ≤ ni ≤ 220；
对于所有评测用例，1 ≤ T ≤ 100000, 1 ≤ ni ≤ 230。
对于 10% 的评测用例，T = 1, 1 ≤ ni ≤ 200；
对于 20% 的评测用例，T = 1, 1 ≤ ni ≤ 2000；
对于 50% 的评测用例，T = 1, 1 ≤ ni ≤ 220；
对于 60% 的评测用例，1 ≤ T ≤ 100000, 1 ≤ ni ≤ 220；
对于所有评测用例，1 ≤ T ≤ 100000, 1 ≤ ni ≤ 230。