Bài tập

Cho dãy số nguyên dương \(A = (a_1, a_2, \dots, a_N)\). Một dãy con của \(A\) là dãy thu được bằng cách xoá đi một số phần tử (có thể không xoá) và giữ nguyên thứ tự các phần tử còn lại.

Một dãy con \(b_1, b_2, \dots, b_k\) được gọi là cấp số cộng công sai \(D\) nếu \(b_{t+1} - b_t = D\) với mọi \(1 \le t < k\). Dãy con chỉ có một phần tử luôn thoả mãn với mọi \(D\).

Bạn được tự do chọn một công sai nguyên \(D\) với \(1 \le D \le 50\). Hãy tìm độ dài lớn nhất của một dãy con của \(A\) là cấp số cộng với công sai \(D\) đã chọn.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

• In ra một số nguyên duy nhất: độ dài lớn nhất tìm được.

Constraints

• \(1 \le N \le 10^5\)
• \(1 \le a_i \le 10^9\)

Sample Input

10
4 9 6 8 10 12 14 3 16 18

Sample Output

8

Explanation

Chọn \(D = 2\), dãy con \(4, 6, 8, 10, 12, 14, 16, 18\) gồm \(8\) phần tử là một cấp số cộng công sai \(2\). Không có cách nào dài hơn.

Cho số nguyên dương \(N\). Liệt kê tất cả các cặp \((A, B)\) với \(1 \le A \le B \le N\) sao cho \(A^2 + B^2\) là một số chính phương.

Input

Một số nguyên \(N\).

Output

Mỗi dòng in một cặp \(A\ B\) (cách nhau một dấu cách), các cặp sắp xếp theo thứ tự từ điển (tăng dần theo \(A\), cùng \(A\) thì tăng dần theo \(B\)). Nếu không có cặp nào thì không in gì.

Constraints

• \(1 \le N \le 10^4\)

Sample Input

17

Sample Output

3 4
5 12
6 8
8 15
9 12
12 16

Hai số nguyên tố \(p\) và \(q\) được gọi là một cặp nguyên tố sexy nếu \(q - p = 6\) (chữ "sexy" đến từ "sex" trong tiếng Latin nghĩa là sáu). Các cặp được liệt kê theo thứ tự tăng dần của số nhỏ \(p\): \((5,11), (7,13), (11,17), (13,19), (17,23), \dots\) Lưu ý một số có thể thuộc hai cặp khác nhau, ví dụ \(11\) thuộc \((5,11)\) và \((11,17)\).

Cho \(T\) câu hỏi, mỗi câu hỏi là một số \(N\). Hãy tìm cặp nguyên tố sexy thứ \(N\).

Input

• Dòng đầu: số nguyên \(T\).
• \(T\) dòng tiếp theo, mỗi dòng một số nguyên \(N\).

Output

In ra \(T\) dòng; dòng thứ \(i\) gồm hai số \(p\) và \(p+6\) của cặp thứ \(N\) tương ứng, cách nhau một dấu cách.

Constraints

• \(1 \le T \le 10^3\).
• \(1 \le N \le 10^4\).

Sample Input

3
4
1
12

Sample Output

13 19
5 11
61 67

Cho xâu \(S\) gồm \(n\) chữ cái Latin in hoa. Xét mọi cặp hai ký tự đứng liền nhau trong \(S\) (vị trí \(i\) và \(i+1\)) và tìm cặp xuất hiện nhiều nhất; các lần xuất hiện được phép chồng lấn. Nếu nhiều cặp cùng đạt số lần lớn nhất, chọn cặp có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng hai chứa xâu \(S\) gồm \(n\) chữ cái Latin in hoa.

Output

In ra cặp chữ cái được chọn.

Constraints

• \(2 \le n \le 10^5\)

Sample Input

8
XYXYXXYZ

Sample Output

XY

Explanation

Các cặp liền kề: \(XY, YX, XY, YX, XX, XY, YZ\). Cặp \(XY\) xuất hiện \(3\) lần, nhiều nhất.