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.

Input

• 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 ~≤10^6~.

Output

• Ghi ra một số nguyên duy nhất là kết quả tìm được.

Scoring

• len(s) là độ dài xâu nhị phân.
• Subtask 1 (40% số điểm): ~1≤k≤len(s)≤500~.
• Subtask 2 (30% số điểm): ~1000≤k≤len(s)≤10000~.
• Subtask 3 (30% số điểm): ~10^5 ≤k≤len(s)≤10^6.~

Example

Input

2
01010 

Output

4

Cho một mảng gồm ~n~ số nguyên và số nguyên ~t~.

Yêu cầu: Tìm mảng con gồm những phần tử liên tiếp dài nhất sao cho tổng tất cả các phần tử của mảng này không quá ~t~. Và số lượng phần tử của mảng này chính là kết quả cần tìm.

Input

• Dòng thứ nhất chứa hai số nguyên ~n~,~t~(~1≤n≤10^5;1≤t≤10^9~)
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~(~1≤a_i≤10^4~)

Output

In ra giá trị cần tìm. Example Test 1

Input

4 4
1 2 1 2

Output

3

Một ngày lướt fb, TN thấy một đôi couple chia sẻ bài bói toán online, rằng đôi couple kia hợp nhau thế nào, yêu nhau ra sao, vân vân và mây mây. Tò mò không biết âm dương ngũ hành, yêu nhau hợp tình nghĩa không, TN cũng bảo Ami cùng mình tham gia bói toán online. Nhưng Ami đời nào tin những thuật toán tào lao ấy? "Bởi vì không một thuật toán nào định nghĩa được tình yêu cả" – Ami nói. Cậu bèn dẫn TN đến cặp thầy bói nổi danh thiên hạ - zerolifes và huyyeuminh_nghia. Hai lúc nào cũng hơn một mà :)).

Sau khi xem chỉ tay, tướng số, ngũ hành, chiêm tinh, zerolifes không nói không rằng. Anh đọc liên tục 1 câu thần chú chỉ toàn những con số vô nghĩa nhưng không giảm. Đột nhiên zerolife dừng lại, huyyeuminhnghia hét lên một số :30. Nhưng 30 là gì ? Không lẽ 2 vị này cao thâm đến mức biết ngày mình và TN quen nhau sao?, Ami thầm nghĩ, Hay 30 là số tỉ USD mà sau này mình tậu được ? Không, không thể ít như vậy được. Không thể kìm nén, Ami thỉnh cầu 2 vị cao nhân. Zerolifes nói :Đơn giản thôi, âm dương hòa hợp, trong cương có nhu, trong nhu có cương, cậu hãy ghi nhớ dãy số của ta và số mà huyyeuminhnghia vừa đọc, hãy đếm xem trong dãy số của ta có bao nhiêu cặp số có tổng đúng bằng k. Nếu số cặp càng lớn, khả năng hai người bền lâu càng nhiều. Tất nhiên, Ami không dám làm ngay lập tức, vì sợ sự thật có thể làm cậu suy sụp.

Tóm lại, có một dãy gồm n số nguyên dương không giảm ~a_1,a_1,a_3,...a_n~ và một số k, Ami muốn đếm số cặp (~i~, ~j~) không trùng nhau mà ~a_i + a_j= k~, lưu ý rằng (i,(~i~, ~j~) và (~j~, ~i~) được tính là 1 cặp.

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~k~ (n(~n ≤10^6,k ≤10^9~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_1,a_3,...a_n~(~a_i≤10^9~).

Output

• Hãy in ra một số nguyên là kết quá của bài toán.

Example

Test 1

Input

4 6
1 1 5 5

Output

4

Test 2

Input

6 5
1 1 1 4 5 5

Output

3

Có n chỗ ngồi được xếp thẳng hàng. Hãy đếm xem có bao nhiêu cách sắp xếp ~n~ người vào ~n~ chỗ ngồi đó.

Input

• Một dòng duy nhất chứa số nguyên dương ~t~(~1≤t≤50~)- Thể hiện số testcase.
• ~t~ dòng tiếp theo, mỗi dòng chứa số nguyên ~n~(~1≤n≤19~).

Output

• Ứng với mỗi testcase in ra đáp án cần tìm.

Example

Input1

2
2
3

Output

2
6