Một siêu máy tính vừa thực hiện xong phép tính giai thừa của một số nguyên dương N (N! = 1 * 2 * ... * N). Tuy nhiên, kết quả này quá lớn và có rất nhiều chữ số 0 ở tận cùng. Để chuẩn bị cho thuật toán nén, máy tính cần biết chính xác có bao nhiêu chữ số 0 liên tiếp ở tận cùng của số N!. Hãy giúp máy tính tính toán điều này.

Input: Một số nguyên dương N (1 <= N <= 10^9).

Output: Số lượng chữ số 0 tận cùng của N!.

Ví dụ:

Input:

10

Output:

2

(Giải thích: 10! = 3628800, có 2 số 0 tận cùng).

Hệ thống radar nhận được một chuỗi tín hiệu S. Một tín hiệu được coi là hoàn hảo nếu nó là một xâu đối xứng (đọc từ trái sang phải hay từ phải sang trái đều giống nhau). Do nhiễu sóng, tín hiệu S có thể bị dư thừa tối đa 1 ký tự. Hãy kiểm tra xem chuỗi S có thể trở thành tín hiệu hoàn hảo bằng cách xóa đi nhiều nhất 1 ký tự hay không.

Input: Một xâu S chỉ gồm các chữ cái in thường (Độ dài <= 10^5).

Output: In ra YES nếu có thể, ngược lại in NO.

Ví dụ:

Input:

abca

Output:

YES

(Giải thích: Xóa ký tự b hoặc c sẽ được xâu đối xứng aca hoặc aba).

Có N khách hàng đang chờ thanh toán tại siêu thị, người thứ i cần T_i phút để thu ngân quét xong mã vạch. Hiện tại chỉ có duy nhất 1 quầy thu ngân mở cửa. Bạn là quản lý và được phép sắp xếp lại thứ tự đứng của N người này trước khi bắt đầu tính tiền. Hãy sắp xếp sao cho tổng thời gian chờ đợi của tất cả N người là nhỏ nhất (Thời gian chờ của người thứ i là tổng thời gian thanh toán của tất cả những người đứng trước họ).

Input:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ti (1 <= Ti <= 10^4).

Output: Tổng thời gian chờ đợi nhỏ nhất của cả hàng.

Ví dụ:

Input:

3
3 1 2

Output:

4

(Giải thích: Xếp theo thứ tự người 2, người 3, người 1 (thời gian 1, 2, 3). Thời gian chờ của người đầu là 0, người hai là 1, người ba là 1+2=3. Tổng chờ = 0 + 1 + 3 = 4).

Thành phố được mô phỏng bằng một lưới tọa độ N dòng và M cột. Bạn cần di chuyển từ góc trên cùng bên trái (1, 1) đến điểm sơ tán ở góc dưới cùng bên phải (N, M) bằng cách chỉ đi sang phải hoặc đi xuống dưới. Tuy nhiên, cơn bão đã làm đổ cây và chặn hoàn toàn K ô trên lưới. Hãy tính số cách di chuyển an toàn đến điểm sơ tán. Vì kết quả rất lớn, hãy in ra phần dư khi chia cho 10^9+7.

Input:

Dòng 1: Ba số nguyên N, M, K (1 <= N, M <= 1000, 0 <= K <= N*M).

K dòng tiếp theo: Mỗi dòng chứa tọa độ r, c của một ô bị chặn (1 <= r <= N, 1 <= c <= M).

Output: Số lượng đường đi modulo 10^9+7.

Ví dụ:

Input:

3 3 1
2 2

Output:

2

Cho một số nguyên dương ~n~, nhiệm vụ của bạn là tìm số nguyên tố đầu tiên lớn hơn ~n~.

Đầu vào:

Dòng đầu tiên chứa số nguyên ~t~: số lượng test.

Tiếp theo là ~t~ dòng, mỗi dòng chứa một số nguyên dương ~n~.

Đầu ra:

Với mỗi test, in ra số nguyên tố nhỏ nhất lớn hơn ~n~.

Ràng buộc:

~1 \le t \le 20~

~1 \le n \le 10^{12}~

Ví dụ :

Input:

5
1
2
3
42
1337

Output:

2
3
5
43
1361