Người ta định nghĩa ~N~ giai thừa là tích ~1 \times 2 \times \ldots \times N~ và kí hiệu là ~N!~. Cho số nguyên dương ~N~ ~(1 \le N \le 10^{18})~. Hiện trên màn hình chữ số bằng ~0~ cuối cùng (bên phải) của ~N!~.

Ví dụ, nhập ~N = 5~ thì kết quả trên màn hình là ~1~ (vì ~5! = 1 \times 2 \times 3 \times 4 \times 5 = 120~, chữ số ~0~ cuối cùng bên phải của ~5!~ là ~1~).

Yêu cầu

Hãy đếm số lượng chữ số ~0~ ở cuối của ~N!~ (giai thừa của ~N~).

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa số nguyên dương ~N~ ~(1 \le N \le 10^{18})~.

Dữ liệu đầu ra

Gồm một dòng duy nhất là kết quả bài toán.

Ràng buộc dữ liệu

• Có 80% số test ứng với 80% số điểm của câu: ~1 \le N \le 10^{12}~;
• Có 20% số test ứng với 20% số điểm của câu: ~10^{12} < N \le 10^{18}~.

Ví dụ

Ví dụ 1

INPUT

5

OUTPUT

1

Giải thích: ~5! = 120 \rightarrow~ kết quả ~1~.

Một số nguyên dương được gọi là số đẹp nếu nó lớn hơn ~10~, mỗi chữ số của nó là số lẻ hoặc là số chính phương. Có nghĩa là mỗi chữ số của nó đều thuộc tập: ~\{0, 1, 3, 4, 5, 7, 9\}~ và tổng tất cả các chữ số của số đó chia hết cho ~3~.

Yêu cầu

Cho một số nguyên dương ~N~ ~(1 \le N \le 10^6)~. Hãy đếm có bao nhiêu số đẹp không vượt quá ~N~. Nếu không có ghi ~-1~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa số nguyên dương ~N~ ~(1 \le N \le 10^6)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng các số đẹp nhỏ hơn hoặc bằng ~N~.

Ràng buộc dữ liệu

• Có 40% số test ứng với 40% số điểm của câu: ~1 \le N \le 10^3~;
• Có 30% số test ứng với 30% số điểm của câu: ~10^3 \le N \le 10^5~;
• Có 30% số test ứng với 30% số điểm của câu: ~10^5 \le N \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

100

OUTPUT

12

Một buổi chiều đẹp trời, Tèo và Tý đang chơi với một dãy số gồm ~N~ phần tử, mỗi phần tử là một con số đầy bí ẩn. Tèo đố Tý: Viết chương trình chỉ giữ lại những số chia hết cho một số ~k~ mà Tý chọn, để dãy số trở nên "đẹp đẽ" và dễ nhìn hơn.

Tý đồng ý, nhưng cậu cũng muốn biết số nguyên dương nhỏ nhất mà chưa xuất hiện trong dãy ban đầu là gì, để biết con số nào còn thiếu trong trò chơi.

Yêu cầu

Hãy viết chương trình giúp bạn Tý:

a) Đếm số lượng và liệt kê các phần tử còn lại.

b) Tìm số nguyên dương nhỏ nhất không xuất hiện trong dãy.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: Hai số nguyên dương ~N~ và ~k~ ~(1 \le N \le 10^6, 1 \le k \le 10^9)~.
• Dòng 2: ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ ~(1 \le a_i \le 10^9)~.

Dữ liệu đầu ra

Gồm ba dòng:

• Dòng 1: Số lượng phần tử còn lại sau khi loại bỏ các số không chia hết cho ~k~.
• Dòng 2: In ra các phần tử còn lại theo thứ tự tăng dần, mỗi phần tử cách nhau bởi dấu cách.
• Dòng 3: Số nguyên dương nhỏ nhất chưa xuất hiện trong dãy ban đầu.

Ràng buộc dữ liệu

• Có 40% số test ứng với 40% số điểm của câu: ~1 \le N \le 10^4~;
• Có 30% số test ứng với 30% số điểm của câu: ~10^4 < N \le 10^5~;
• Có 30% số test ứng với 30% số điểm của câu: ~10^5 < N \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

10 5
1 2 4 5 7 15 30 55 8 25

OUTPUT

5
5 15 25 30 55
3

Nam rất thích dãy những con số, đặc biệt dãy số nguyên dương. Cậu tò mò muốn biết sau khi dãy đã sắp xếp tăng dần thì có bao nhiêu cặp chỉ số ~(i, j)~ với ~1 \le i < j \le N~ sao cho ~a[j] - a[i] \le K~.

Yêu cầu

Hãy giúp Nam tính số lượng các cặp ~(i, j)~ thỏa mãn điều kiện trên.

Dữ liệu đầu vào

Gồm ~2 \times T + 1~ dòng:

• Dòng đầu tiên chứa số nguyên ~T~ là số bộ dữ liệu kiểm tra ~(1 \le T \le 60)~.
• Mỗi bộ dữ liệu gồm:
  1. Dòng đầu chứa hai số nguyên ~N~ và ~K~ ~(1 \le N \le 10^5; 0 \le K \le 10^9)~.
  2. Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^9)~.

Dữ liệu đầu ra

Gồm ~T~ dòng, với mỗi bộ dữ liệu, in ra số lượng cặp ~(i, j)~ thỏa mãn điều kiện của bài toán.

Ràng buộc dữ liệu

• Có 50% số test ứng với 50% số điểm của câu: ~1 \le T \le 40; 1 \le N \le 10^3~;
• Có 30% test khác ứng với 30% số điểm của câu: ~1 \le T \le 10; 10^3 < N \le 10^4~;
• Có 20% test còn lại ứng với 20% số điểm của câu: ~1 \le T \le 10; 10^4 < N \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

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

OUTPUT

7
5

Giải thích:

• Bộ dữ liệu ~1~: Sau sắp xếp tăng dần: ~\{1, 2, 3, 4, 5\}~; Có các cặp chỉ số ~(1,2), (1,3), (2,3), (2,4), (3,4), (3,5), (4,5)~ thỏa mãn ~\rightarrow~ tổng ~= 7~.
• Bộ dữ liệu ~2~: Các cặp chỉ số ~(1,2), (1,3), (2,3), (2,4), (3,4)~ thỏa mãn ~\rightarrow~ tổng ~= 5~.