Một số nguyên dương \(N\) được gọi là hợp số đơn giản nếu nó có thể viết được dưới dạng: \(N=p_1 \cdot p_2\) với \(p_1,p_2\) đều là các số nguyên tố.

Cho số nguyên dương \(N\). Kiểm tra xem \(N\) có phải là hợp số đơn giản hay không?

Input

• Dòng thứ nhất chứa số nguyên \(T\) (\(1\le T\le 10\)) thể hiện testcase.
• \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(N\) (\(1\le N\le 10^9\)).

Output

• Ứng với mỗi giá trị của \(N\), in ra Yes nếu \(N\) là hợp số đơn giản, ngược lại in ra No.

Scoring

• Subtask 1 (\(20\%\) số điểm): \(N\le 10^3\).
• Subtask 2 (\(20\%\) số điểm): \(N\le 10^6\).
• Subtask 3 (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
4
5

Yes
No

Cho dãy \(a\) gồm \(n\) số nguyên, bạn phải đặt giữa \(n\) số nguyên này \(2\) phép nhân và \(n-3\) phép cộng sao cho kết quả biểu thức là lớn nhất.

Ví dụ: với \(n=5\) và dãy \(a_i\) là \(4,7, 1, 5, 3\) thì bạn có thể có các biểu thức:

• \(4 + 7 \cdot 1 + 5 \cdot 3\)
• \(4 \cdot 7 +1 + 5 \cdot 3\)

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(4 \leq n \leq 10^3\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\) (\(1 \leq a_i \leq 10^4\)).

Output

• Ghi một số nguyên dương duy nhất là giá trị lớn nhất của biểu thức thu được.

Example

5
4
7
1
5
3

44

Đây là bài toán interactive.

Các bạn có thể tìm hiểu về dạng này này tại đây.

ami có một số \(n, n\leq10000\). Các bạn sẽ không biết số này. Các bạn cần đoán số này dùng không quá 30 thao tác sau:

• Các bạn có thể hỏi ami một dãy số \(A\) gồm \(k\) phần tử nguyên dương \((k\leq5000)\). ami sẽ trả về một số bất kì \(A_i\) trong dãy số mà \(n\) chia hết cho \(A_i\) (\(n \% A_i = 0\)).

Để hỏi ami, các bạn cần in ra câu hỏi có dạng sau :

• \(?\space n \space A_1 \space A_2 \space A_3 ... A_n\).

Ví dụ, để hỏi dãy có \(4\) phần tử là \(1\space2\space 3\space 4\), các bạn cần in ra "? 4 1 2 3 4" (dấu ngoặc kép chỉ để nhấn mạnh).

Đương nhiên, sau khi in ra câu hỏi, các bạn cần phải xuống dòng và flush câu hỏi này. Sau đó ami sẽ trả lời lại các bạn, câu trả lời có dạng sau :

• \(x\).

Nếu \(x = −1\), điều này có nghĩa rằng câu hỏi mà các bạn hỏi là không hợp lệ. Các bạn cần dừng chương trình ngay và nhận kết quả là "Wrong answer". Nếu chương trình không dừng lại, các bạn sẽ nhận được một thông báo bất kì, vì các bạn đang tương tác với ami đã đi gánh team.

Nếu \(x = 0\), điều này có nghĩa rằng, không tồn tại \(x\) mà \(n\) chia hết \(A_x\).

Nếu \(x\gt0\), ami sẽ đảm bảo rằng \(n\) chia hết \(A_x\).

Sau khi các bạn đã đoán ra số n, các bạn cần thông báo cho ami. Thông báo như sau :

• ! n.

Ví dụ, số các bạn đoán là \(69\), các bạn cần thông báo "! 69" (dấu ngoặc kép chỉ để nhấn mạnh).

Example

1
2
4
3
0 

? 4 4 2 3 1
? 4 1 2 3 4
? 4 1 2 3 4
? 4 1 2 3 4
? 4 69 96 69 96
! 12

dungde99 vừa vẽ ra một bảng số nguyên dương gồm \(M\) hàng và \(N\) cột, các hàng được đánh số từ \(1\) đến \(M\) từ trên xuống và các cột được đánh số từ \(1\) đến \(N\) từ trái sang phải. dungde99 ký hiệu ô \((i, j)\) là ô nằm ở giao điểm của hàng \(i\) và cột \(j\) của bảng. Sau đó, dungde99 đưa ra bộ bốn số \(x_1\), \(y_1\), \(x_2\) và \(y_2\) rồi đố Flow God tìm một đường đi tối ưu từ ô \(\left(x_1, y_1\right)\) đến ô \(\left(x_2, y_2\right)\), tức là một đường đi xuất phát tại ô \(\left(x_1, y_1\right)\) mà tại mỗi bước Flow God chỉ có thể di chuyển sang ô kề bên phải hoặc ô kề bên dưới của ô hiện tại, đồng thời tổng các số ghi ở các ô trên đường đi (bao gồm cả ô \(\left(x_2, y_2\right)\)) phải nhỏ nhất có thể. Flow God nhanh chóng trả lời được câu đố đầu tiên của dungde99 nhưng sau đó dungde99 lại hỏi tiếp hàng loạt câu hỏi dạng tương tự như vậy khiến Flow God phải bó tay trong sự lúng túng. Các bạn hãy giúp Flow God giải đáp tất cả các câu đố này nhé!

Input

• Dòng đầu tiên chứa một số nguyên \(x\).
• Dòng tiếp theo chứa một số nguyên \(n\).

Output

• Một dòng duy nhất chứa một nguyên là \(x ^ n\) sau khi chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

• \(1 \leq x \leq 10 ^ 9\)
• \(1 \leq n \leq 10 ^ 9\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10 ^ 6\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 

9

4
5 

1024

Giáo sư Wu Zi Mu đã tiếp tục ra bài tập cho học sinh lớp \(1\) như sau:

"Định nghĩa \(S(N)\) là tổng tất cả các ước nguyên dương của \(N\). Ví dụ: \(S(12)=1+2+3+4+6+12=28\)

Cho \(Q\) truy vấn, mỗi truy vấn gồm số nguyên dương \(N\). Tính \(S(N!^{3})\) mod \(1200000090\)"

Học sinh nghĩ mãi không ra. Các bạn hãy giúp học sinh trả lời \(Q\) truy vấn trên.

Input

• Gồm \(Q+1\) dòng:
• Dòng đầu tiên gồm số \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(N\).

Output

• Gồm \(Q\) dòng là kết quả của \(Q\) truy vấn theo thứ tự từ trên xuống dưới, in ra từng dòng.

Constraints

• \(1 \leq N \leq 4.10^{7}\)
• \(1 \leq Q \leq 10\)

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N \leq 5, Q \leq 3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^{4}, Q \leq 10\).
• Subtask #3 (\(30\%\) số điểm): \(N \leq 10^{6}, Q \leq 10\).
• Subtask #4 (\(30\%\) số điểm): \(N \leq 4.10^{7}, Q \leq 4\), tổng các \(N\) trong \(Q\) truy vấn không quá \(4.10^{7}\).

Example

2
4 
3  

40920
600