U124697 CF848E Days of Floral Colours 加强版

题目背景

参见原题。

题目描述

同原题

输入格式

第一行一个整数 $T$ 表示测试数据组数。接下来 $T$ 行，每行一个正整数表示每组的 $n$。

输出格式

$T$ 行，每行一个正整数，第 $i$ 行表示第 $i$ 组数据的答案。

说明/提示

### 数据范围：对于 $12\%$ 的数据：$T=1,n\leq 5\times 10^4$。对于 $25\%$ 的数据：$T=1,n\leq 5\times 10^6$。对于 $39\%$ 的数据：$T\leq 100,n\leq 5\times 10^6$。对于 $100\%$ 的数据：$T\leq 100,n\leq 10^{18}$。