题目：寻找产生最长 Collatz 序列的起始数

欧拉 第 14 题。

问题描述

定义如下的整数序列（称为 Collatz 序列）：

• 若当前项 n 为偶数，则下一项为 n → n / 2
• 若当前项 n 为奇数，则下一项为 n → 3n + 1

例如： 从 13 开始，可得到以下序列：

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

该序列共包含 10 项。

虽然 Collatz 猜想尚未被严格证明，但一般认为所有正整数的序列最终都会到达 1。

任务要求

给定一个整数 N，请在所有 起始数 < N 的 Collatz 序列中：

• 找到 链长最长的起始数；
• 如果存在多个起始数的链长相同，则输出其中 最大的起始数。

注意： 序列中的项可能会远远超过 N，这不会影响计算。

输入格式

• 第一行包含一个整数 T，表示测试用例数量。
• 接下来 T 行，每行包含一个整数 N。

输出格式

对于每个测试用例，输出一个整数，表示小于 N 的起始数中，能产生最长 Collatz 链的那个数。

数据范围

• 1 ≤ T ≤ 10⁴
• 1 ≤ N ≤ 5 × 10⁶

样例输入

3
10
9
20

样例输出

9
9
19

样例解释

对于 N = 10，满足起始数 < 10 的序列中：

• 9 的序列长度为 20 多步，是前 1~9 中最长的 因此输出 9。

对于 N = 20，最长链来自起始数 19，因此输出 19。