Cho hai xâu X, Y. Xâu X có độ dài bằng 3, xâu Y có độ dài n ~(3 < n ≤ 10000)~. Xâu X được gọi là xuất hiện trong xâu Y nếu tồn tại số tự nhiên i ~(0 ≤ i ≤ n - 3)~ thỏa mãn:

$$X[0] = Y[i]; X[1] = Y[i+1]; X[2] = Y[i+2]$$

Yêu cầu:

Cho hai xâu X, Y chỉ gồm các chữ cái in thường a, b, c, ..., z. Hãy lập trình đếm số lần xuất hiện của xâu X trong xâu Y.

Dữ liệu:

• Dòng đầu ghi xâu X có độ dài bằng 3;
• Dòng thứ hai ghi xâu Y có độ dài bằng n ~(3 < n ≤ 10000)~.

Kết quả:

Ghi ra một số nguyên là số lần xuất hiện của xâu X trong xâu Y.

Ví dụ:

Giải thích:

Trích xuất nội dung từ ảnh (đã thay thế ký tự toán học):

Giải thích:

• Test 1: Xâu X = "abc", xâu Y = "ehabcopabcm", tồn tại số tự nhiên là ~i = 2~, thỏa mãn:
  X[0] = Y[2]; X[1] = Y[3]; X[2] = Y[4]
  và tồn tại số tự nhiên ~i = 7~ thỏa mãn:
  X[0] = Y[7]; X[1] = Y[8]; X[2] = Y[9]
  nên kết quả là 2.

• Test 2: Xâu X = "abc" không xuất hiện trong xâu Y = "udacbk" nên kết quả là 0.

Ràng buộc:

Cho một dãy gồm n số nguyên dương ~a_1, a_2, ..., a_n~.

Yêu cầu:

Hãy lập trình đếm số các số nguyên dương trong dãy đã cho có tổng các ước là một số chẵn.

Dữ liệu:

• Dòng đầu ghi số nguyên dương ~n (1 \leq n \leq 1000)~ là số phần tử của dãy;
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 1000, i=1,2,...,n~) các số cách nhau một dấu cách.

Kết quả:

Ghi ra số các số nguyên dương của dãy đã cho có tổng các ước là số chẵn.

Ví dụ:

Giải thích:

• Test 1: số ~1~ có một ước là ~1~ nên không thỏa mãn, số ~4~ có các ước là ~1, 2, 4~ có tổng các ước bằng ~7~ nên không thỏa mãn, số ~8~ có các ước là ~1, 2, 4, 8~ có tổng các ước bằng ~15~ nên cũng không thỏa mãn, số ~5~ có hai ước là ~1, 5~ có tổng bằng ~6~ nên là số thỏa mãn. Vì vậy kết quả là ~1~.

• Test 2: số ~2~ có hai ước là ~1, 2~ có tổng bằng ~3~ nên không thỏa mãn, số ~10~ có các ước là ~1, 2, 5, 10~ có tổng các ước bằng ~18~ nên thỏa mãn, số ~5~ có hai ước là ~1, 5~ có tổng bằng ~6~ nên là số thỏa mãn. Vì vậy, kết quả là ~2~.

Ràng buộc:

Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ và hai số nguyên dương ~m, M~. Mỗi dãy ~a_i, a_{i+1}, a_{i+2}, ..., a_j~ với ~1 \leq i \leq j \leq n~ được gọi là dãy con liên tiếp của dãy đã cho.

Yêu cầu:

Hãy lập trình đếm số các dãy con liên tiếp của dãy số đã cho có tổng các số lớn hơn hoặc bằng ~m~ và nhỏ hơn hoặc bằng ~M~.

Dữ liệu:

• Dòng đầu ghi ba số nguyên ~n, m, M~ (~1 \leq n \leq 10^5; 1 \leq m, M \leq 10^{18}, m < M~).
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 1000, i = 1, 2, ..., n~).

Các số trên cùng một dòng cách nhau bởi một dấu cách.

Kết quả:

Ghi ra một số nguyên là số các dãy con liên tiếp thỏa mãn có tổng các số lớn hơn hoặc bằng ~m~ và nhỏ hơn hoặc bằng ~M~.

Ví dụ:

Giải thích:

• Test 1: Các dãy con thoa mãn là: 3 2; 2 4; 4 2; 3 2 4;2 4 2; 4 2 1;2 1 2;2 4 2 1; 4 2 1 2.

Ràng buộc:

• Có ~\frac{2}{5}~ số test thỏa mãn: ~1 < n \leq 100, M \leq 10^9~;

• ~\frac{2}{5}~ số test khác thỏa mãn: ~100 < n \leq 5000, M \leq 10^9~;

• ~\frac{1}{5}~ số test còn lại thỏa mãn: ~5000 < n \leq 100000, M \leq 10^{18}~.

Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Ước chung lớn nhất của dãy số nguyên ~a_1, a_2, ..., a_n~ là số nguyên dương ~d~ thỏa mãn:

i) ~d~ là ước của tất cả các số ~a_1, a_2, ..., a_n~.

ii) ~d~ là số lớn nhất trong tất cả các ước của ~a_1, a_2, ..., a_n~.

Ví dụ như 20, 8, 12 có các ước chung là 1, 2, 4 nên 4 là ước chung lớn nhất của 20, 8, 12.

Xét một phép biến đổi dãy số nguyên ~a_1, a_2, ..., a_n~ như sau:

• Chọn hai số bất kì trong dãy (gọi là hai số ~A~ và ~B~) và một số nguyên tố ~p~ sao cho ~A~ chia hết cho ~p~. Sau đó xóa số ~A~ đi và thay vào đó là số ~\frac{A}{p}~, xóa số ~B~ đi và thay vào đó là số ~B.p~.

Bạn được phép thực hiện phép biến đổi đã cho với số lần tùy ý để biến đổi dãy ~a_1, a_2, ..., a_n~ thành dãy mới ~b_1, b_2, ..., b_n~.

Yêu cầu:

Hãy lập trình tính giá trị lớn nhất (gọi là ~d~) có thể của ước chung lớn nhất của dãy ~b_1, b_2, ..., b_n~ qua một số phép biến đổi dãy và số phép biến đổi ít nhất (gọi là ~c~) để nhận được giá trị lớn nhất đó.

Dữ liệu:

• Dòng đầu ghi số nguyên dương ~n~ (~1 \leq n \leq 100~);
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 1000000, i = 1,2,...,n~). Các số trên cùng một dòng cách nhau bởi một dấu cách.

Kết quả:

Ghi ra giá trị lớn nhất ~d~ có thể và số phép biến đổi ít nhất ~c~ để nhận được giá trị ~d~, hai số cách nhau bởi một dấu cách.

Ví dụ:

Giải thích:

Test 1:
Thực hiện một phép biến đổi dãy như sau:

• Chọn ~A = 72, B = 8, p = 3~, thay số ~A~ bằng số ~\frac{A}{p} = \frac{72}{3} = 24~, thay số ~B~ bằng số ~B \cdot p = 8 \cdot 3 = 24~.
• Dãy số đã cho biến đổi thành dãy mới ~24, 24~, có ước chung lớn nhất là ~24~.
• Hoặc có thể chọn ~A = 8, B = 72, p = 2~, thì dãy đã cho được biến đổi thành dãy ~4, 144~, có ước chung lớn nhất là ~4~.
• Có thể biến đổi ~8, 72~ thành nhiều dãy mới. Tuy nhiên, trong trường hợp này, cách biến đổi đầu tiên là cách thu được dãy mới có ước chung lớn nhất có thể là ~24~ qua một phép biến đổi dãy.
• Vì vậy, kết quả là 24 1.

Test 2:

• Chọn ~A = 4, B = 5, p = 2~, thì dãy đã cho được biến đổi thành dãy ~2, 10, 6, 7, 8~.
• Ta lại chọn tiếp ~A = 8, B = 7, p = 2~, thì dãy ~2, 10, 6, 7, 8~ được biến đổi thành dãy ~2, 10, 6, 14, 4~.
• Dãy mới ~2, 10, 6, 14, 4~ có ước chung lớn nhất là ~2~.
• Vì vậy, kết quả là 2 2.

Ràng buộc:

• Có ~\frac{1}{2}~ số test của bài thỏa mãn: ~n = 2~.
• ~\frac{1}{2}~ số test còn lại thỏa mãn: ~2 < n \leq 100~.