Dãy phân số

Sau một thời gian nghiên cứu, Nam đã đưa ra một phương pháp mã hóa các số nguyên thông qua dãy các phân số. Với số nguyên dương \(k\), một dãy hữu hạn các phân số \(a_i\) được định nghĩa như sau:

• \(a_1 = \frac{1}{k}\);
• \(a_i = \frac{x_i}{y_i} = \frac{x_{i-1}+1}{y_{i-1}-1}\) khi \(i > 1\) với \(\frac{x_i}{y_i}\) là một phân số tối giản;
• Khi \(a_i\) đạt đến một giá trị nguyên \(n\), dãy phân số kết thúc (\(y_i = 1\)).

Nam mã hóa hàm số \(f(k) = n\). Ví dụ: với \(k=20\) có dãy biến đổi sau:
$ \frac{1}{20} \to \frac{2}{19} \to \frac{3}{18} = \frac{1}{6} \to \frac{2}{5} \to \frac{3}{4} \to \frac{4}{3} \to \frac{5}{2} \to \frac{6}{1} = 6 $

Kết quả \(f(20) = 6\).

Yêu cầu: Cho số nguyên dương \(x\), bạn hãy giúp Nam tính \(f(x^3)\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(T \le 100\)) là số lượng giá trị \(x\) cần tính \(f(x^3)\);
• Mỗi dòng trong số \(T\) dòng tiếp theo chứa một số nguyên dương \(x\).

Output

• Gồm \(T\) dòng, mỗi dòng là giá trị \(f(x^3)\) tương ứng với số nguyên dương \(x\) trong dữ liệu vào.

Example

2
3
4

6
12

Scoring

• Số test ứng với 50% số điểm của bài có: \(x \le 100\);
• Số test khác ứng với 30% số điểm của bài có: \(x \le 10^4\);
• Số test còn lại ứng với 20% số điểm của bài có: \(x \le 10^6\).