时空限制

1S/256M

题目描述

给定一个正整数 $M$，请求出满足以下条件的所有整数对 $(A, B)$ 中，整数 $A$ 的总和：

1. $A \geq 1$，$B \geq 1$；
2. $A^B = M$。

格式

输入格式

本题含有多组测试数据。

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

接下来 $T$ 行，每行包含一个整数 $M$。

输出格式

对于每组测试数据，输出一行一个整数表示答案。

样例

样例输入 #1

5
8
32
64
1000000
10617447681

样例输出 #1

10
34
78
1001110
10617551043

样例解释 #1

对于第一组数据 $M=8$，满足条件的 $(A, B)$ 只有 $(8, 1)$ 和 $(2, 3)$，此时 $A$ 的取值为 $8$ 和 $2$，总和为 $10$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \leq T \leq 5$，$2 \leq M \leq 10^{14}$。