Một số \(n\) bất kì luôn có \(1\) tập ước số không chứa \(1\) riêng của nó, dù là số nguyên tố hay hợp số. Ví dụ như số \(6\) có tập ước số không chứa \(1\) là \((2;3;6)\), còn số \(420\) có tập ước số không chứa \(1\) là \((2;3;4;5;6;7;10;12;14;15;20;21;28;35;60;84;105;140;210;420)\). Trinh mới học thêm về số nguyên tố và hợp số, liền về nhà lấy giấy ra viết \(1\) số \(420\) và dãy ước không chứa \(1\) của chính số \(420\) ấy. Viết xong rồi, cậu nhìn lại thì thắc mắc: Ủa? Sao có nhiều đoạn số liên tiếp thế này? Có đoạn có tới \(6\) số liên tiếp lận? (Nếu bạn thắc mắc là đoạn nào, thì đó là đoạn \((2;3;4;5;6;7)\) đấy) Rồi cô nghĩ tiếp: Thế nếu mình muốn tạo ra \(1\) số \(n\) bất kì mà trong dãy ước ấy có ít nhất \(1\) đoạn liên tiếp có \(k\) số thì làm thế nào nhỉ? Cô bí bài này nên cô muốn nhờ các bạn ở LQDOJ rằng: Cho \(1\) số tự nhiên \(k(k≤10^6)\), hãy tìm số nguyên dương \(n\) bé nhất có thể mà trong dãy ước số không chứa \(1\) của nó có ít nhất \(1\) đoạn số liên tiếp có chiều dài không nhỏ hơn \(k\).

Input

• Dòng \(1\) nhập số \(q\) chỉ số truy vấn\((q<=100)\), sau đó là \(q\) dòng, mỗi dòng nhập duy nhất \(1\) số \(k\)

Output

• Mỗi truy vấn xuất kết quả mod cho \(10^9+7\).

Example

1
2

6

Ràng buộc: 50% test có \(k<=100\)