Tìm số

Gọi khoảng cách giữa hai số nguyên dương \(a\) và \(b\) là \(|a - b|\). \(F(x)\) là số lượng ước nguyên dương của số nguyên dương \(x\) tính cả \(1\) và \(x\).

Ví dụ: Số \(3\) có \(2\) ước nguyên dương là \(1\) và \(3\). Ta có \(F(3) = 2\) và khoảng cách giữa hai ước là \(1\).

Yêu cầu: Cho số nguyên dương \(k\), tìm số nguyên dương \(x\) nhỏ nhất sao cho \(F(x) = 4\) và khoảng cách giữa hai ước bất kỳ của \(x\) tối thiểu là \(k\).

Input

Dữ liệu vào:

• Dòng \(1\): Chứa số nguyên dương \(T\) (\(T \le 10^6\)) là số bộ dữ liệu;

• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k\) (\(k \le 10^6\)) tương ứng với một bộ dữ liệu vào.

Ràng buộc:

• Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: \(T = 1\), \(k \le 5\);

• Có \(30\%\) số test khác ứng với \(30\%\) số điểm thỏa mãn: \(T = 1\), \(k \le 10^2\);

• Có \(20\%\) số test khác ứng với \(20\%\) số điểm thỏa mãn: \(T \le 10\), \(k \le 10^5\);

• Có \(20\%\) số test còn lại ứng với \(20\%\) số điểm thỏa mãn: \(T \le 10^6\), \(k \le 10^6\).

Output

In ra \(T\) dòng, mỗi dòng ghi một số nguyên dương \(x\) là kết quả tìm được tương ứng với một bộ dữ liệu vào.

Example

Input:

3
1
2
2025

Output:

6
15
8223539

Note

Với \(k = 1\): số \(6\) là số nguyên dương nhỏ nhất có \(4\) ước dương là \(1, 2, 3, 6\) và khoảng cách giữa hai ước bất kỳ tối thiểu là \(1\).

Với \(k = 2\): số \(15\) là số nguyên dương nhỏ nhất có \(4\) ước dương là \(1, 3, 5, 15\) và khoảng cách giữa hai ước bất kỳ tối thiểu là \(2\).