Cho một số tự nhiên ~N (N<10^{64}~).

Yêu cầu: Hãy viết chương trình nhập vào một số nguyên N và tính tổng các chữ số của số tự nhiên N vừa nhập vào.

Ví dụ: Nhập vào N = 1234. Tổng các chữ số của nó là 10.

Input:

1234

Output:

10

Cho hai số nguyên dương ~N, X (N, X≤ 10^{18})~.

Yêu cầu: Hãy viết chương trình tìm số lượng bội của N sao cho bội của N không vượt quá giá trị của X.

Ví dụ: N=2, X=7. Số lượng bội của N là 3 (vì có 2, 4 và 6 là bội của N).

Dữ liệu vào: Từ tệp văn bản MULT.INP có cầu trúc:

• Dòng đầu ghi số nguyên dương K(K ≤ 100) là số lượng bộ dữ liệu;

• Tiếp theo là K dòng, mỗi dòng tương ứng với bộ dữ liệu chứa hai số N và X.

Kết quả : Ghi ra tệp văn bản MULT.OUT gồm K dòng, mỗi dòng tương ứng với bộ dữ liệu vào là số lượng bội của N tìm được.

Ràng buộc:

• Có 60% test ứng 60% số điểm của bài với ~N, X ≤ 10^5, K=1~;

• Có 20% test ứng 20% số điểm của bài với ~N, X ≤ 10^5~;

• Có 20% test khác ứng với 20% số điểm còn lại của bài với ~N, X ≤ 10^{18}~

Input 01:

1
2 7

Output 01:

3

Input 02:

2
2 7
5 10

Output 02:

3
2

Cho dãy số nguyên gồm N phần tử a1, a2, ..., an. Gọi Q là số lượng phần tử của dãy con liên tiếp dài nhất có tổng bằng 0.

Yêu cầu: Hãy viết chương trình tìm Q.

Ví dụ: N=5 với dãy: 2, 1, -2, 3, -2 thì dãy con dài nhất có tổng bằng 0 là: 1,-2, 3, -2 và Q=4.

Dữ liệu vào: Từ tệp văn bản ZERO.INP có cấu trúc:

• Dòng đầu tiên chứa số tự nhiên ~N(1 ≤ N ≤ 10^6)~;

• Dòng tiếp theo chứa dãy số nguyên gồm N phần từ ai, a2, ..., an. ~(|ai| ≤ 10^9)~, các số cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản ZERO.OUT gồm một số Q duy nhất.

Input:

5
2 1 -2 3 -2

Output:

4

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự "0" hoặc "1". Xâu v gọi là xâu con của w nếu xâu v có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu w. Ví dụ: xâu "010" có các xâu con là "0", "1", "0", "01", "10", "010".

Yêu cầu: Cho trước một giá trị K, hãy đếm xem có bao nhiêu xâu con chứa đúng K ký tự "1".

Dữ liệu vào: Từ tệp văn bản SUBSTR. INP có cầu trúc:

• Dòng 1 chứa một số nguyên ~K (0 ≤ K ≤ 10^6)~;

• Dòng 2 chứa một xâu nhị phân có độ dài không quá ~10^6~.

Kết quả: Ghi ra tệp văn bản SUBSTR.OUT gồm một số nguyên duy nhất là kết quả tìm được.

Ràng buộc:

• Có 60% test ứng 60% số điểm của bài với K ≤ 100 và độ dài của xâu không quá 100;

• Có 20% test ứng 20% số điểm của bài với K ≤ 254 và độ dài của xâu không quá 254;

• Có 20% test khác ứng với 20% số điểm còn lại của bài với ~K ≤ 10^6~ và độ dài của xâu không quá ~10^6~.

Input 01:

2
01010

Output 01:

4

Có 4 xâu chứa 2 ký tự "1" là: "101", "0101", "1010", "01010".

Input 02:

3
1111

Output 02:

2