Cho ~q~ truy vấn. Mỗi truy vấn gồm ~2~ số nguyên dương ~l~ và ~r~. Hãy đếm số lượng số nguyên tố từ ~l~ đến ~r~.

Input

• Dòng đầu tiên chứa số nguyên ~q~ (~q \leq 10^5~) - số lượng truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ (~1 \leq l \leq r \leq 10^6~).

Output

• In ra ~q~ dòng, dòng thứ ~i~ chứa kết quả của truy vấn ~i~.

Sample Test

Input:

5
4 20
2 10
1 18
1 100
1 1000

Output:

6
4
7
25
168

Cho dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Bạn được phép thay đổi bất kì một số trong dãy trên thành một số nguyên dương khác bất kì. Hãy tìm cách thay đổi tối ưu để ước chung lớn nhất của dãy trên lớn nhất có thể, hay ~gcd(a_1, a_2, ..., a_n)~ là lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Output

• Gồm một số nguyên duy nhất là kết quả bài toán.

Sample Input

3
4 3 8

Sample Output

4

Note

Có thể thay đổi ~a_2=3~ thành ~a_2 = 16~. Từ đó ~gcd(a_1, a_2, a_3) = gcd(4, 16, 8) = 4~.

Cho một mảng gồm ~n~ số nguyên, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng ~x~.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~x~: kích thước của mảng và tổng ~x~.
• Dòng tiếp theo có ~n~ số nguyên ~a_1, a_2, \ldots, a_n~: nội dung của mảng.

Output

• In một số nguyên: số lượng đoạn con được yêu cầu.

Constraints

• ~1 \le n \le 2 \cdot 10^5~
• ~-10^9 \le x, a_i \le 10^9~

Sample Tests

Input

5 7
2 -1 3 5 -2

Output

2

Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy đếm số đoạn con ~[l, r]~ ~(1 \le l < r \le n)~ sao cho ~a_l + a_{l+1} + ... + a_r~ chia hết cho ~d~

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~d~ ~(1 \le n, d \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(-10^9 \le a_i \le 10^9)~

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Input

5 4
1 3 -2 3 -5

Sample Output

4

Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy đếm số đoạn con ~[l, r]~ ~(1 \le l \le r \le n)~ sao cho trung bình cộng của đoạn con ~[l, r]~ là ~k~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ ~(1 \le n \le 10^5, |k| \le 10^6)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(-10^6 \le a_i \le 10^6)~

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Input

5 2
1 3 -2 3 -5

Sample Output

1

Bạn được cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ gồm các số nguyên từ ~0~ đến ~9~. Một dãy con ~a_l, a_{l+1}, \dots, a_{r-1}, a_r~ được gọi là tốt nếu tổng các phần tử trong dãy con bằng với chính độ dài của dãy con (~\sum_{i=l}^r a_i = r - l + 1~).

Ví dụ, nếu ~a = [1, 2, 0]~ thì có ~3~ dãy con tốt: ~a_{1\dots1} = [1], a_{2\dots3} = [2, 0], a_{1\dots3} = [1, 2, 0]~.

Hãy tìm số lượng dãy con tốt của dãy ~a~.

Input

• Dòng đầu tiên chứa duy nhất số nguyên dương ~n~ (~1 \leq n \leq 10^5~) - độ dài của mảng ~a~.
• Dòng thứ hai chứa một chuỗi gồm ~n~ chữ số, trong đó chữ số thứ ~i~ là ~a_i~ (~0 \leq a_i \leq 9~).

Output

In ra một số nguyên duy nhất là số lượng dãy con tốt của dãy ~a~.

Sample Test

Input:

3
120

Output:

3

Input:

5
11011

Output:

6

Input:

6
600005

Output:

1

Cho một mảng gồm ~n~ số nguyên, nhiệm vụ của bạn là tìm tổng giá trị lớn nhất trong một đoạn con liên tiếp với độ dài giữa ~a~ và ~b~.

Input

• Dòng đầu vào đầu tiên có ba số nguyên ~n~, ~a~ và ~b~: kích thước của mảng và độ dài tối thiểu và tối đa của đoạn con.
• Dòng thứ hai có ~n~ số nguyên ~x_1, x_2, \ldots, x_n~: các giá trị mảng.

Output

• In một số nguyên: tổng đoạn con lớn nhất.

Constraints

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le a \le b \le n~
• ~-10^9 \le x_i \le 10^9~

Sample Tests

Input

8 1 2
-1 3 -2 5 3 -5 2 2

Output

8

Bob gửi cho Alice một dãy số nguyên gồm ~N~ phần tử: ~A_1,A_2,...,A_N~ đây là thông tin về một kho báu. Một đoạn con ~(L,R)~ của dãy là một dãy gồm các phần tử liên tiếp ~A_L,A_{L+1},...,A_R~ với ~1 \leq L < R \leq N~, đoạn con ~(L,R)~ được gọi là chứa thông tin quan trọng nhất nếu:

• Phần tử đầu tiên bằng phần tử cuối cùng (~A_L=A_R~).
• Tổng các phần tử của đoạn là lớn nhất có thể.

Yêu cầu: Hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa số nguyên ~A_1,A_2,...,A_N\text{ }(|A_i|\leq 10^9,1\leq i\leq N)~.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng của đoạn con chứa thông tin quan trọng nhất.

Constraints

• ~N\leq 10^5~

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~N\leq 10^2~
• Subtask ~2~ (~30\%~ số điểm): ~N\leq 10^3~
• Subtask ~3~ (~30\%~ số điểm): ~N\leq 10^5~

Sample Tests

Input

7
3 3 3 3 1 11 1

Output

13

Cho một dãy xâu ~S~ gồm ~n~ kí tự từ ~1~ đến ~9~. Hãy đếm số lượng cặp ~(i, j)~ ~(1 \le i \le j \le n)~ thỏa mãn các chữ số trong đoạn ~[i, j]~ tạo thành một số nguyên chia hết cho ~2023~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - độ dài xâu ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ kí tự của xâu ~S~.

Output

Gồm số nguyên duy nhất là kết quả bài toán.

Sample Test

Input:

10
2427624276

Output:

3

Note

Các cặp ~(i, j)~ thỏa mãn là: ~(1, 5)~ ~(6, 10)~, ~(1, 10)~.