Kiểm tra năng lực

UIT Algo Bootcamp 2025 - Kỳ huấn luyện mùa thu đã chính thức khai giảng, chào đón những bạn trẻ đam mê lập trình thi đấu. Để giúp các trại sinh làm quen với nhịp độ và thử thách, ban tổ chức đưa ra một bài toán đặc biệt.

Chúng ta định nghĩa \(d(i)\) là tổng các ước số nguyên dương của một số nguyên dương \(i\). Ví dụ, \(d(6) = 1 + 2 + 3 + 6 = 12\).

Bài toán hôm nay yêu cầu các bạn, với một số nguyên dương \(c\) cho trước, hãy tìm số nguyên dương \(n\) nhỏ nhất sao cho \(d(n) = c\). Bài toán này đòi hỏi các bạn phải vận dụng kiến thức về lý thuyết số và các thuật toán hiệu quả để xử lý dữ liệu lớn. Đây không chỉ là một bài kiểm tra kiến thức, mà còn là cơ hội để các bạn học cách phân tích bài toán, tìm ra chiến lược tối ưu và làm quen với áp lực thời gian của một kỳ thi lớn.

Hãy thể hiện tinh thần đồng đội và sự quyết tâm của mình, chinh phục bài toán này và sẵn sàng cho những thử thách tiếp theo của Bootcamp nhé!

Yêu cầu: Cho một số nguyên dương \(c\), tìm số nguyên dương \(n\) nhỏ nhất sao cho tổng các ước của \(n\) bằng \(c\).

Input

• Dòng đầu tiên chứa duy nhất số nguyên dương \(Q\) (\(1 \le Q \le 10000\)), là số truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(c\) (\(1 \le c \le 10^7\)).

Output

• Với mỗi truy vấn, in ra "-1" nếu không tồn tại số nguyên dương \(n\) thỏa mãn, ngược lại in ra số \(n\) nhỏ nhất tìm được.

Example

12
1
2
3
4
5
6
7
8
9
10
39
691

1
-1
2
3
-1
5
4
7
-1
-1
18
-1

Scoring

• Có \(50\%\) số test có \(Q, c \le 100\).
• Có \(50\%\) số test còn lại không có ràng buộc gì thêm.