A 星际通讯 (telecom)

题目描述

在遥远的未来，数据传输成为星际通信的核心技术。银河联盟设计了两种信息打包方式来高效传输数据包：

1. 点发模式（Pulse Mode）：每次点发传输 1 个字节，耗时 1 秒。
2. 波发模式（Wave Mode）：科学家可以选择一个正整数 $x$，波发将花费 $2^x$ 秒，但一次可恰好传输 $10^x$ 字节。

为了降低传输时间，每次传输任务中，通信工程师们都要精确计算最短传输时间。你作为联盟技术顾问，需要帮助他们完成这项工作。

你将会收到多个传输请求，每个请求指定了需要传输的字节数。请你为每个请求计算出完成它所需的最短时间。

输入格式

• 第一行是一个整数 $T$（$1 \leq T \leq 50000$），表示传输请求数量。
• 接下来 $T$ 行，每行一个整数 $r$（$1 \leq r \leq 10^{18}$），表示该请求需要传输的字节数。

输出格式

• 输出 $T$ 行，每行一个整数，表示完成该请求所需的最少时间（以秒计）。

样例

样例输入 1

5
23
61
62
114514
1919810

样例输出 1

7
13
14
106
474

数据范围与约定

对于 $100\%$ 的数据，满足：

• $1 \leq T \leq 5 \times 10^4$
• $1 \leq r \leq 10^{18}$