Bài này Giống bài ~CTNOWN~ nhưng giới hạn lớn hơn

Cho nguyên dương ~N (1 \le N \le 3500)~. Hãy tìm cách phân tích ~N~ thành tổng của một số số nguyên dương sao cho bội số chung nhỏ nhất của chúng là lớn nhất có thể.

Input

Dòng đầu tiên là ~T~ : Số test.

~T~ dòng sao mỗi dòng là một số nguyên dương ~N (1 \le N \le 3500)~.

Output

Với mỗi test cần in ra một số là bội chung nhỏ nhất tìm được.

Sample Input

1
10

Sample Output

30