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à ~|3 - 1| = 2~.

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

Vào từ file văn bản FDIV.INP:

• 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.

Output

Ghi ra file văn bản FDIV.OUT gồm ~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.

Ví dụ

Input

3
1
2
2025

Output

6
15
8223539

Giải thích

• 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~.
• 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~.

Giới hạn

• ~1 \le T \le 10^6~
• ~1 \le k \le 10^6~

Các nhóm test:

• 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~.