# 分数次幂递推

预估时间限制：1.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

一个求值服务接到许多整数查询。每个答案又依赖两个较小参数的答案，请计算这些查询的精确值。

(本故事由GPT-6重写)

## 形式化问题描述

函数 $F$ 的定义域和值域都是非负整数，并满足

$$F(x)=3F\left(\max\{\lfloor x^{4/5}\rfloor-1,0\}\right)+2F\left(\left\lfloor\frac{x}{2}\right\rfloor\right)+x$$

分数次幂表示实数意义下的幂，$\lfloor\cdot\rfloor$ 表示向下取整。等式也适用于零，从而 $F(0)=0$ .给出 $N$ 个参数 $a_i$ ，求每个 $F(a_i)$ 的精确整数值，不取模。

## 输入格式

第一行整数 $N$ ，表示查询数。第二行 $N$ 个整数 $a_1,\ldots,a_N$ .

## 输出格式

输出一行 $N$ 个整数，以空格分隔，依次表示各个查询的答案。

## 样例

### 样例 1

### 输入

```text
5
0 1 1000000000 5000 2
```

### 输出

```text
0 1 12422138161640 8422275 4
```

### 样例 2

### 输入

```text
6
0 0 1 2 3 4
```

### 输出

```text
0 0 1 4 8 24
```

## 样例解释

第二组中，$F(1)=1$ ，$F(2)=4$ ，$F(3)=8$ ；因为 $\lfloor4^{4/5}\rfloor-1=2$ ，所以 $F(4)=3F(2)+2F(2)+4=24$ .重复查询零时都输出零。

## 数据范围与保证

对所有数据，$1\le N\le10^5$ ，$0\le a_i\le10^9$ .查询可以重复。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |