Chủ đề số nguyên tố là chủ đề mà bạn An rất thích. Hôm nay, cô giáo giao cho bạn An một bài tập về số nguyên tố như sau:

Cho số nguyên dương $n(1\le n\le {10}^5)$, em hãy đếm xem có bao nhiêu số tự nhiên nhỏ hơn hoặc bằng $n$ mà số đảo ngược của nó là số nguyên tố. Em hãy lập trình giúp bạn An giải quyết bài toán trên.

Dữ liệu:

• Một dòng duy nhất chứa số nguyên dương $n$.

Kết quả:

• Một dòng duy nhất là kết quả của bài toán.

Ví dụ:

Sample Input 1

10

Sample Output 1

4

Sample Input 2

15

Sample Output 2

7

Giải thích:

Trong ví dụ 2: Từ $1$ đến $15$ có các số $2,3,5,7,11,13,14$ là các số mà đọc ngược là số nguyên tố.

Bạn Cừu mới học môn Hóa học được biết rằng: Một phân tử nước $H_{2}O$ gồm có hai nguyên tử Hydro và một nguyên tử Oxy. Hôm nay, bạn Cừu tự hỏi nếu như có số lượng Hydro và Oxy nhất định thì có thể có bao nhiêu phân tử nước. Em hãy lập trình tính số lượng phân tử nước tối đa mà bạn ấy có thể nhận được.

Biết rằng nếu mỗi nguyên tử $O$ và $H$ đã sử dụng liên kết với nhau thì không thể kết hợp với nguyên tử khác.

Dữ liệu:

• Một dòng duy nhất chứa một xâu $S$ (độ dài không quá $1000$ ký tự) chỉ gồm các ký tự $H$ và $O$.

Kết quả:

• Đưa ra một số nguyên là số lượng phân tử nước tối đa mà Cừu có thể nhận được.

Ví dụ:

Sample Input 1

HHOHHO

Sample Output 1

2

Sample Input 2

HHHHHHOOOO

Sample Output 2

3

Trong giờ học hoạt động trải nghiệm, cô giáo muốn giáo dục cho các bạn học sinh Tiểu học đi xe đạp theo đúng luật an toàn giao thông.

Lớp học có $n$ học sinh, đánh số thứ tự từ $1$ đến $n$, trọng lượng của các bạn học sinh là $a_1,a_2,\dots ,a_n$ (kg). Cô giáo cần chọn ra hai bạn học sinh làm mẫu cho những học sinh khác. Hai bạn học sinh được chọn sẽ đèo nhau và đi theo cung đường đã được vẽ sẵn trên sân trường. Xe đạp có trọng tải là $P$ (kg), vì vậy cần chọn ra hai bạn học sinh có tổng trọng lượng nhỏ hơn hoặc bằng $P$.

Yêu cầu: Bạn hãy giúp cô giáo Tiểu học của chúng ta đếm số cách chọn hai học sinh để làm mẫu cho các bạn học sinh khác.

Dữ liệu:

• Dòng đầu tiên chứa $2$ số nguyên $n$ và $P(2\le n\le 2\times {10}^5,1\le P\le {10}^9)$ - số lượng học sinh trong lớp và trọng tải của xe đạp;
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n(1\le a_i\le {10}^9)$ - tương ứng là trọng lượng của $n$ bạn học sinh.

Kết quả:

• In ra một số nguyên $C$ là số cách chọn một cặp học sinh để làm mẫu.

Ví dụ:

Sample Input

5 9
4 8 4 1 10

Sample Output

4

Ràng buộc:

• Subtask 1: Có $60\mathrm{\%}$ số test đầu tiên $n\le 1000$.
• Subtask 2: Có $40\mathrm{\%}$ số test cuối cùng không có ràng buộc gì.

Có một con mèo, $k$ con chuột và một cái hang chuột trên một trục tọa độ $Ox$. Con mèo nằm ở điểm $0$, cái hang nằm ở điểm $n$. Tất cả các con chuột nằm giữa con mèo và cái hang: Con chuột thứ $i$ nằm ở điểm $x_i(0<x_i<n)$. Tại mỗi điểm có thể có nhiều con chuột.

Trong một giây, những điều sau đây sẽ thực hiện liên tục:

• Đầu tiên, có đúng một con chuột di chuyển sang bên phải $1$ đơn vị. Nếu con chuột đến hang, nó sẽ trốn được mèo (tức là con chuột sẽ không di chuyển đến bất kỳ điểm nào nữa và sẽ không bị con mèo ăn thịt).

• Sau khi chuột di chuyển xong mèo di chuyển sang phải $1$ đơn vị. Nếu ở vị trí mới của mèo có chuột, mèo sẽ ăn thịt chúng (những con chuột bị ăn thịt sẽ loại ra khỏi trục số).

Các hoạt động của mèo và chuột sẽ kết thúc khi mèo đến được vị trí $n$ (tất nhiên những con chuột trốn trong hang tại vị trí $n$ sẽ không bị ăn thịt).

Mỗi giây, bạn có thể chọn một con chuột sẽ di chuyển. Hỏi tối đa bao nhiêu con chuột lọt được vào hang mà không bị ăn thịt?

Dữ liệu:

Dòng đầu tiên chứa số nguyên dương $t(1\le t\le 10)$ là số lượng bộ test. Mỗi bộ test sẽ có dạng như sau:

• Dòng đầu tiên chứa số nguyên $n$ và $k(1\le n\le {10}^9;1\le k\le 5\times {10}^5)$;
• Dòng thứ hai chứa $k$ số nguyên $x_1,x_2,\dots ,x_k(1\le x_i<n)$ là vị trí của các con chuột.

Kết quả:

Gồm $t$ dòng, mỗi dòng chứa một giá trị $P$ là số lượng những con chuột đã trốn vào hang tương ứng với dữ liệu Input.

Ví dụ:

Sample Input

2
10 6
8 7 5 4 9 4
2 8
1 1 1 1 1 1 1 1

Sample Output

3
1

Ràng buộc:

• Subtask 1: Có $20\mathrm{\%}$ số test đầu tiên $k=2$;
• Subtask 2: Có $30\mathrm{\%}$ số test tiếp theo $n\le 500,k\le 10000$;
• Subtask 3: Có $50\mathrm{\%}$ số test cuối cùng không có ràng buộc gì.