Nguồn: Học sinh Giỏi THCS Hà Nội năm 2014 - 2015

Cho phương trình \(ax + by = c\), với \(a, b, c\) là các số nguyên dương.

Yêu cầu: Tìm số lượng cặp \((x, y)\), với \(x, y\) nguyên dương, là nghiệm của phương trình.

Input

Dữ liệu vào từ tệp văn bản CAU1.INP:

• Gồm một dòng duy nhất chứa ba số nguyên dương \(a, b, c\), mỗi số không vượt quá \(10^9\).

Output

Kết quả ra tệp văn bản CAU1.OUT:

• Ghi ra số lượng các cặp nghiệm nguyên dương \((x, y)\) của phương trình.

Examples

2 4 20

4

Note

• Các cặp nghiệm nguyên dương của phương trình \(2x + 4y = 20\) là: \((2, 4), (4, 3), (6, 2), (8, 1)\).

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2014 - 2015

Cho \(n\) số nguyên \(a_1, a_2, …, a_n\). Người ta muốn chia \(n\) số nguyên này thành các nhóm, trong mỗi nhóm hiệu của số lớn nhất và số nhỏ nhất không vượt quá số nguyên dương \(h\) cho trước.

Yêu cầu: Xác định số lượng nhóm ít nhất khi chia nhóm \(n\) số nguyên đã cho thỏa mãn điều kiện trên.

Dữ liệu vào từ tệp văn bản CAU2.INP:

• Dòng đầu chứa hai số nguyên dương \(n\) và \(h\), \(n \leq 10^3, h \leq 10^9;\)
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) \((1 \leq i \leq n)\) chứa số nguyên \(a_i\), có giá trị tuyệt đối không vượt quá \(10^9\).

Output

Kết quả ra tệp văn bản CAU2.OUT:

• Ghi ra số lượng nhóm ít nhất tìm được.

Examples

6 3
-7
27
-5
26
28
-6

2

Note

• Có thể chia \(6\) số đã cho thành hai nhóm. Nhóm thứ nhất gồm các số thứ \(1\), thứ \(3\), thứ \(6\) và nhóm thứ hai là các số còn lại. Hai nhóm này đều có hiệu của số lớn nhất và số nhỏ nhất là \(2\), nhỏ hơn \(3\).

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2014 - 2015

Cho trước số nguyên dương \(t\). Người ta tạo một số nguyên dương \(x\) bằng cách sau: Trước hết, biểu diễn số \(t = p_1 \times p_2 \times p_k\), trong đó \(p_i\) (\(1 \leq i \leq k\)) là các số nguyên tố (\(k\) có thể bằng \(1\)); tiếp theo viết các số \(p_1, p_2, \dots, p_k\) theo một thứ tự nào đó liên tiếp nhau để nhận được số nguyên dương \(x\).

Yêu cầu: Tìm giá trị lớn nhất của \(x\).

Dữ liệu vào từ tệp văn bản CAU3.INP:

• Chứa số nguyên dương \(t\) không vượt quá \(10^9\).

Output

Kết quả ra tệp văn bản CAU3.OUT:

• Ghi ra giá trị \(x\) lớn nhất tìm được.

Examples

476

72217

Note

• Có \(476 = 2 \times 2 \times 7 \times 17\) nên số \(x\) lớn nhất là \(72217\).

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2014 - 2015

Cho trước bảng số \(A\) gồm \(m\) hàng, \(n\) cột. Mỗi ô trong bảng số chứa một số nguyên dương gọi là giá trị của ô. Tất cả các ô (ít nhất là \(2\) ô) có cùng giá trị, kề cạnh hoặc kề đỉnh tạo thành một vùng số. Số lượng ô trong một vùng số gọi là diện tích của vùng số đó.

Yêu cầu: Tính số lượng vùng số có trong bảng \(A\) và diện tích của vùng số lớn nhất.

Dữ liệu vào từ tệp văn bản CAU4.INP:

• Dòng đầu chứa hai số nguyên dương \(m, n\), mỗi số không vượt quá \(100\);
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên dương, mỗi số không vượt quá \(100\).

Output

Kết quả ra tệp văn bản CAU4.OUT:

• Dòng đầu ghi số lượng các vùng số có trong bảng \(A\);
• Dòng thứ hai ghi diện tích của vùng số lớn nhất.

Examples

5 6
1 2 1 4 5 4
1 3 1 4 5 4 
3 1 2 3 3 4 
2 2 4 5 3 3 
2 2 3 2 1 1

8
5

Note

• Có \(8\) vùng số gồm: \(2\) vùng số \(1\); \(1\) vùng số \(2\); \(2\) vùng số \(3\); \(2\) vùng số \(4\); \(1\) vùng số \(5\). Trong \(8\) vùng số trên, diện tích vùng số lớn nhất là \(5\).