Sau tiết số học, thầy có giao cho Bờm một bài toán như sau:

Cho một số nguyên dương ~n~ và ~n~ số nguyên dương ~a_{1}, a_{2}, \ldots, a_{n}~. Việc của Bờm là tìm hai số trong dãy số đã cho sao cho ước chung lớn nhất của hai số đó càng lớn càng tốt.

Yêu cầu: Cho số nguyên dương ~n~ và ~n~ số nguyên dương ~a_{1}, a_{2}, \ldots, a_{n}~. Hãy giúp Bờm tìm ước chung lớn nhất đó.

Dữ liệu:

• Dòng đầu tiên ghi một số nguyên dương ~n\left(2 \leq n \leq 10^{5}\right)~;
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_{1}, a_{2}, \ldots, a_{n}\left(1 \leq a_{i} \leq 10^{6}\right)~.

Kết quả:

• Ghi ra một số duy nhất là ước số lớn nhất mà Bờm tìm được.

Ví dụ:

Sample Input

5
3 14 15 7 9

Sample Output

7

Giới hạn:

• Subtask 1: ~50 \%~ các test có ~n=2~;
• Subtask 2: ~25 \%~ các test có ~n \leq 10^{3}~;
• Subtask 3: ~25 \%~ các test có ~n \leq 10^{6}~.

Số đặc biệt là một số nguyên dương có tính chất sau:

• Số đó là một số nguyên tố;
• Ở dạng nhị phân chứa đúng ~k~ bít ~1~.

Yêu cầu: Cho trước ~n, k~. Hãy xác định có bao nhiêu số đặc biệt không vượt quá ~n~ và ở dạng nhị phân chứa đúng ~k~ bit ~1~.

Dữ liệu:

• Gồm một dòng duy nhất chứa hai số nguyên dương ~n, k~.

Kết quả:

• Ghi ra một số là kết quả tìm được.

Ví dụ:

Sample Input

100 4

Sample Output

7

Giải thích:

• Ví dụ: ~7~ số đó là: ~23, 29, 43, 53, 71, 83, 89~.

Giới hạn:

• Subtask 1: ~50 \%~ các test có ~n \leq 10^{3}~;
• Subtask 2: ~50 \%~ các test có ~n \leq 10^{6}~.

Cho một số nguyên dương ~N~, gọi ~M~ là tập các số nhận được từ ~N~ bằng cách giữ nguyên hoặc xóa đi một số chữ số của ~N~.

Ví dụ: ~N=2301~ thì tập ~M = \{0 ; 1 ; 2 ; 3 ; 20 ; 21 ; 23 ; 30 ; 31 ; 201 ; 230 ; 231 ; 301 ; 2301\}~.

Yêu cầu: Cho trước ~N\left(2 \leq N \leq 10^{9}\right)~. Hãy tìm số nguyên tố lớn nhất trong tập ~M~.

Dữ liệu:

• Gồm một dòng duy nhất chứa một số nguyên dương ~N\left(2 \leq N \leq 10^{9}\right)~.

Kết quả:

• Ghi một số là số nguyên tố lớn nhất trong tập ~M~. Nếu không có số nguyên tố nào trong tập ~M~ thì ghi ra ~-1~.

Ví dụ:

Sample Input 1

2301

Sample Output 1

31

Sample Input 2

97

Sample Output 2

97

Sample Input 3

666

Sample Output 3

-1

Giới hạn:

• Subtask 1: ~50 \%~ số test có ~n \leq 10^{6}~;
• Subtask 2: ~50 \%~ số test có ~n \leq 10^{9}~.

Các chú nhóc XI TRUM ở Vương quốc Happy land có một thói quen là khi gặp nhau các chú thường đọc tên của nhau (bằng cách đánh vần từng chữ cái của tên), sau khi đọc tên của một ai đó, tâm trạng của người đọc sẽ hạnh phúc hay không hạnh phúc phụ thuộc vào tên mà XI TRUM theo quy tắc sau đây:

• Nếu tên gọi có chứa các chữ cái ~'S','D'~ sau khi đánh vần chữ cái này, tâm trạng của người đọc sẽ hạnh phúc;
• Nếu tên gọi có chứa chữ cái ~'H'~ sau khi đánh vần chữ cái này, tâm trạng của người đọc sẽ không hạnh phúc;
• Nếu tên gọi có chứa các chữ cái ~'A', 'E', 'I','O', 'U'~ sau khi đánh vần chữ cái này, tâm trạng của người đọc sẽ hạnh phúc chuyển thành không hạnh phúc và ngược lại. Ví dụ: với tên là ~SMMMM, DNNPPP~ là những tên mà sau khi đánh vần sẽ mang lại hạnh phúc cho XI TRUM còn tên ~HTTTTG~ sẽ mang lại tâm trạng không hạnh phúc cho XI TRUM; các tên ~SONG, EM~ sau khi đọc xong sẽ đảo ngược tâm trạng của các XITRUM.

Tâm trạng của XI TRUM khi bắt đầu ngày mới là hạnh phúc, tâm trạng hạnh phúc hay không hạnh phúc sẽ ảnh hưởng đến hiệu suất làm việc của XI TRUM là tốt hay xấu. Nên Tộc trưởng của tộc XI TRUM muốn đặt tất cả các tên của XITRUM thành tên mà sau khi đọc tên này sẽ mang lại tâm trạng hạnh phúc cho người đọc tên đó. Trước khi chọn các tên để đặt thì tộc trưởng muốn biết với số nguyên dương ~n~ thì có bao nhiêu cái tên có ~n~ chữ cái (các chữ cái trong bảng chữ cái tiếng anh in hoa) sau khi đọc xong sẽ mang lại tâm trạng hạnh phúc cho người đọc.

Yêu cầu: Cho trước số nguyên dương ~n~, hãy giúp tộc trưởng tính xem có bao nhiêu cái tên có ~n~ chữ cái sẽ mang lại tâm trạng hạnh phúc cho người đọc tâm trạng ban đầu của người đọc là hạnh phúc.

Dữ liệu:

• Gồm một dòng duy nhất chứa một số nguyên dương ~1 \leq n \leq 10^{18}~.

Kết quả:

• Ghi một số nguyên là kết quả tìm được, do kết quả rất lớn chỉ cần đưa ra số dư khi lấy kết quả chia cho ~10^{9}+7~.

Ví dụ:

Sample Input 1

1

Sample Output 1

20

Sample Input 2

2

Sample Output 2

442

Sample Input 3

11

Sample Output 3

145418665

Giới hạn:

• Subtask 1: ~25 \%~ các test có ~n \leq 5~;
• Subtask 2: ~50 \%~ các test có ~n \leq 10^{6}~;
• Subtask 3: ~25 \%~ các test có ~n \leq 10^{18}~.