Hai số nguyên tố được gọi là song sinh nếu chúng cách nhau \(2\) đơn vị.

Cho số nguyên dương \(N\). Hãy liệt kê các cặp số nguyên tố song sinh nhỏ hơn \(N\).

Input

• Gồm một số nguyên dương \(N\) duy nhất (\(N \leq 10^{7}\)).

Output

• In ra các cặp số thỏa mãn trên từng dòng, với số bé hơn đứng ở trước số lớn hơn. Các cặp cần được sắp xếp theo thứ tự tăng dần.

Sample Test

15

3 5
5 7
11 13

Cho một mảng \(A\) có \(n\) phần tử là các số tự nhiên nhỏ hơn \(1000000\).

Bạn hãy dùng 3 nhắt cắt, cắt mảng thành 4 mảng con liên tiếp, sao cho chênh lệch giữa đoạn có tổng lớn nhất và đoạn có tổng nhỏ nhất được giảm thiểu nhất (nhỏ nhất) có thể.

Input

• Dòng đầu tiên gồm số \(4 \le n \le 1000000\)
• Dòng thứ hai gồm \(n\) số lần lượt là \(A_1, A_2, A_3, \dots..., A_n\)

Output

Một số duy nhất là đáp án của bài toán

Ví dụ:

Sample Input:

6
2 1 2 1 4 3

Sample Output:

1

Bạn đang tham gia chương trình Tìm người thông minh. Trong lúc giải lao, BTC tổ chức trò chơi sau:

Trên bàn có một dãy \(n\) món quà có giá trị nguyên tương ứng là \(G_1, G_2, G_3, \dots, G_n\).

Bạn sẽ nhận một giỏ quà rỗng để đựng quà, và được phép thực hiện các thao tác sau đây:

• Lấy đi món quà nằm ở phía ngoài cùng bên trái của dãy, và cho vào giỏ
• Lấy đi món quà nằm ở phía ngoài cùng bên phải của dãy, và cho vào giỏ
• Chọn một món quà trong giỏ và để lại vào phía ngoài cùng bên trái của dãy
• Chọn một món quà trong giỏ và để lại vào phía ngoài cùng bên phải của dãy

Không dùng quá \(k\) thao tác, hãy tìm cách để nhận được tổng giá trị quà cao nhất.

Input

• Dòng đầu tiên chứa số \(n\) \((n \le 10^3)\)
• Dòng tiếp theo chứa lần lượt \(n\) số \(G_1, G_2, G_3, \dots, G_n\) là giá trị của \(n\) món quà của dãy quà \((|G_i| \le 10^7)\).
• Dòng cuối cùng chứa số \(k\) \((k \le 2 \times 10^3)\).

Output

Một số duy nhất là kết quả tốt nhất đạt được của bài toán.

Ví dụ:

Sample Input:

4 3
9 -10 -2 -4

Sample Output:

9

Giải thích: Lấy duy nhất một món quà số 9.

Subtask

• Subtask 1: \(n \le 50\)
• Subtask 2: \(n \le 100\)
• Subtask 3: \(n \le 1000\)

Tổ chức Bóng đèn vừa tạo ra một thiết bị mới - Một dãy các bóng đèn.

Thiết bị gồm có \(n\) công tắc đánh số từ \(1\) tới \(n\), và \(m\) bóng đèn đánh số từ \(1\) tới \(m\). Mỗi công tắc có hai trạng thái: bật/tắt, và mỗi bóng đèn cũng vậy.

Công tắc thứ \(i\) có thể điều khiển \(k_i\) bóng đèn: \(S_{i,1}, S_{i,2}, S_{i,3}, \dots, S_{i,k_i}\). Mỗi khi gạt công tắc (dù bật hoặc tắt), các bóng đèn bị ảnh hưởng sẽ tự động chuyển từ bật thành tắt, từ tắt thành bật.

Ban đầu, toàn bộ các công tắc và bóng đèn đều bị tắt. Hỏi, có bao nhiêu điều khiểncách bật/tắt công tắc sao cho toàn bộ các bóng đèn đều được bật?

Hai cách điều khiển được gọi là khác nhau nếu tồn tại một công tắc mà ở cách này thì được bật, còn cách kia thì bị tắt.

Input

• Dòng đầu tiên chứa lần lượt hai số \(n, m\) \((n, m \le 10)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa:
• Số đầu tiên là \(k_i\), biểu thị số bóng đèn mà công tắc thứ \(i\) điều khiển. \((k_i \le m)\)
• \(k_i\) số tiếp theo lần lượt là \(S_{i,1}, S_{i,2}, S_{i,3}, \dots, S_{i,k_i}\), là chỉ số của các bóng đèn mà công tắc thứ \(i\) điều khiển, các số này khác nhau đôi một.

Output

Một dòng duy nhất là đáp án - số cách điều khiển bật/tắt \(n\) công tắt để tất cả \(m\) bóng đèn đều bật.

Ví dụ:

Sample Input:

5 2
3 1 2 5
2 2 3
1 0

Sample Output:

8

Ban đầu, bạn được chọn một số nguyên tố \(x\) bất kỳ. Sau đó, bạn có thể thực hiện phép biến đổi sau với số lần tùy thích:

Chọn số nguyên \(d>1\) tùy ý và gán \(x \leftarrow d \times x+1\).

Bạn có một con số mục tiêu là \(n\). Hỏi có bao nhiêu \(x\) khác nhau có thể chọn lúc đầu để đạt được mục tiêu là \(n\) sau 1 số lần biến đổi (hoặc không biến đổi lần nào)?

Input

Gồm 1 dòng duy nhất chứa số \(n\).

Output

Gồm 1 dòng duy nhất chứa đáp án.

Subtask

\(40\%\) bộ test có \(2 \le n \le 10^3\)

\(60\%\) còn lại có \(10^3 < n \le 10^5\)

Ví dụ

Input

5

Output

2

Giải thích

Có hai giá trị \(x\) thỏa mãn:

• Chọn \(x=2\), sau đó thực hiện thao tác với \(d=2\)
• Chọn \(x=5\)