HSG THCS Hà Nội 2018

Một số nguyên dương được gọi là đặc biệt nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố.

Ví dụ: \(12\) là số đặc biệt vì \(1^2 + 2^2 = 5\) là số nguyên tố.

Yêu cầu: Cho số nguyên dương \(n\). Hãy tìm số đặc biệt nhỏ nhất lớn hơn \(n\).

Input

• Dữ liệu vào từ tệp văn bản CAU1.INP chứa số nguyên dương \(n\) (\(1 \le n \le 10^9\)).

Output

• Ghi vào tệp văn bản CAU1.OUT số đặc biệt nhỏ nhất lớn hơn \(n\).

Example

11

12

Để động viên khích lệ học sinh tham gia dự thi học sinh giỏi năm nay, trường ITS có chuẩn bị \(n\) phần quà cho \(n\) thí sinh dự thi. Trên hộp quà thứ \(i\) có ghi số nguyên \(a_i\). Sau khi tặng quà cho các thí sinh, trường sẽ có thêm những cặp quà đặc biệt cho mỗi cặp thí sinh có cặp số trên hộp quà là \(a_i, a_j\) (\(i \neq j\)) mà \(a_i + a_j = 0\).

Yêu cầu: Hãy cho biết trường phải chuẩn bị thêm bao nhiêu cặp quà đặc biệt.

Input

• Dữ liệu vào từ tệp văn bản CAU2.INP:
  • Dòng thứ nhất chứa số nguyên dương \(n\) (\(1 < n \le 10^6\)).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) đôi một khác nhau (\(|a_i| \le 10^5, 1 \le i \le n\)).

Output

• Ghi ra tệp văn bản CAU2.OUT số lượng cặp quà đặc biệt.

Example

7
6 -3 0 1 -1 3 2

2

Cho hai xâu \(X\) và \(Y\) độ dài tối đa mỗi xâu không quá \(1000\) kí tự, bao gồm các chữ cái và các chữ số.

Yêu cầu: Hãy tìm xâu \(Z\) là xâu con chung liên tiếp của hai xâu \(X\) và \(Y\) gồm toàn các chữ số tạo thành một số có giá trị lớn nhất.

Input

• Dữ liệu vào từ tệp văn bản CAU3.INP:
  • Dòng thứ nhất chứa xâu \(X\);
  • Dòng thứ hai chứa xâu \(Y\).

Output

• Ghi ra tệp văn bản CAU3.OUT xâu \(Z\) tìm được.

Example

ab123abcba57
cba12abcbad23

23

Thành phố ABC có một khu đô thị gồm nhiều khối chung cư cao tầng được mô tả trong bản đồ hình chữ nhật gồm \(m\) dòng và \(n\) cột. Các dòng được đánh số từ \(1\) đến \(m\) và các cột được đánh số từ \(1\) đến \(n\). Ô ở dòng thứ \(i\) và cột thứ \(j\) ghi một số nguyên dương \(a_{ij}\) mô tả số tầng của một khối chung cư ở hàng thứ \(i\) và cột \(j\). Một khối chung cư được định nghĩa là một tập hợp các ô có đáy tạo thành một miền gồm những ô vuông kề cạnh có giá trị lớn hơn \(0\).

Để chỉnh trang khu đô thị người ta muốn sơn toàn bộ các bề tường xung quanh (không cần phải sơn mái chung cư) tất cả các khối chung cư bằng một loại sơn mới bền và đẹp hơn. Ban quản lý khu đô thị muốn xác định số lượng các khối chung cư, tổng số diện tích phải sơn, diện tích của khối chung cư phải sơn lớn nhất (mỗi mặt của một tầng được tính là một đơn vị diện tích).

Yêu cầu: Với bản đồ trên, hãy giúp ban quản lý khu đô thị xác định số lượng các khối chung cư, tổng số diện tích phải sơn, diện tích của khối chung cư phải sơn lớn nhất.

Input

• Dữ liệu vào từ tệp văn bản CAU4.INP:
  • Dòng thứ nhất chứa hai số nguyên dương \(m\) và \(n\) (\(1 < m \le 500, 1 < n \le 500\));
  • \(m\) dòng tiếp theo, mỗi dòng ghi \(n\) số nguyên \(a_{ij}\), là số ghi trên ô vuông ở dòng thứ \(i\) và cột thứ \(j\) (\(0 \le a_{ij} \le 10^3, 1 \le i \le m, 1 \le j \le n\)).

Output

• Ghi ra tệp văn bản CAU4.OUT:
  • Dòng thứ nhất ghi số lượng các khối chung cư;
  • Dòng thứ hai ghi tổng số diện tích cần sơn;
  • Dòng thứ ba ghi diện tích khối chung cư cần sơn lớn nhất.

Example

4 5
0 0 0 2 0
0 0 0 1 0
0 1 3 0 0
0 0 0 0 0

2
24
14