Bạn được cho 1 dãy gồm N số nguyên dương và S ~(1 ≤ N≤ 10^6,1 ≤ S≤ 10^1~~^8)~.

Yêu cầu: Tìm tổng một đoạn con liên tiếp dài nhất sao cho đoạn con đó không vượt quá S.

Input

• Dòng thứ nhất là số nguyên dương N và S

• Dòng thứ hai là N số nguyên dương ¬(1 ≤ a[i] ≤ 10^9)¬.

Output

-Là kết quả theo yêu cầu đề bài.

Giới hạn

Không giới hạn gì thêm

Ví dụ

Sample input

7 20
2 6 5 3 6 8 9

Sample output

4

Cho một mảng arr các số nguyên dương được sắp xếp theo thứ tự tăng dần và một số mảng kArr. Với mỗi giá trị thuộc mảng kArr, in ra số nguyên dương thứ kArr bị thiếu trong mảng arr.

Dữ liệu vào: Đọc ở file văn bản KTH.INP:

Dòng đầu chứ số nguyên dương ~N~ và K lần lượt là số phần tử của mảng arr và mảng kArr.

~N~ dòng tiếp theo mỗi dòng chứa giá trị ~arr_i~ (Mỗi giá trị ~arr_i~ là khác nhau).

~K~ dòng tiếp theo mỗi dòng chứa giá trị ~kArr_i~.

Dữ liệu ra: Ghi ra file văn bản KTH.OUT gồm ~K~ dòng, mỗi dòng là số nguyên dương bị thiếu thỏa đề bài.

Giới hạn: ~1≤N≤10^5~; ~1≤K≤10^3~; ~1≤arr_i, kArr_i≤ 10^5~

Ví dụ:

KTH.INP

5 1
2
3
4
7
11
5

KTH.OUT

9

*Giải thích: *

Các số nguyên dương còn thiếu là [1,5,6,8,9,10,12,13,...]. Số nguyên dương còn thiếu thứ 5 là 9.

Huỳnh Bá Hoài An có thói quen khi trả lời ~Yes~ với người khác, anh ta sẽ lặp lại từ đó nhiều lần liên tiếp.

Trong lúc nói chuyện với anh ta, vì tiếng ồn nên bạn chỉ nghe thấy được một phần của câu trả lời. Nghĩa là khi anh ấy trả lời ~YesYes~ thì bạn có thể nghe thấy ~sYes~, ~esY~, ~YesYes~, ~e~, nhưng bạn không thể nghe ~Yess~, ~YES~ hoặc ~se~.

Cho một chuỗi ~S~, xác định xem chuỗi ~S~ có phải chuỗi con của chuỗi ~YesYes...~ hay không (~Yes~ lặp lại nhiều lần liên tiếp).

Một chuỗi ~a~ được gọi là chuỗi con của ~b~ nếu ~a~ được lấy từ ~b~ bằng việc xóa đi (~1~ vài hoặc ~0~) kí tự đầu và xóa đi (~1~ vài hoặc ~0~) kí tự cuối của chuỗi ~b~.

Input

• Dòng đầu tiên chứa số nguyên T thể hiện số testcase ~(1 \le T \le 1000)~,
• ~T~ dòng tiếp theo mỗi dòng là một chuỗi ~S~ ~(1 \le |S| \le 50)~, |S| là chiều dài của chuỗi |S|

Output

• Gồm T dòng, mỗi dòng in "YES" nếu S là chuỗi con, ngược lại in "NO".

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

4
YES
YesYe
sYe
top1nhan500k

Output

NO
YES
YES
NO

Giải thích ví dụ

Ở testcase thứ nhất, xâu "YES" không phải là xâu con theo đề bài.

Ở testcase thứ hai, xâu "YesYe" là xâu con của xâu "YesYes".

Ở testcase thứ ba, xâu "sYe" là xâu con của xâu "YesYes".

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử ~1~ và ~1~, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó.

~F(1) = F(2) = 1~

~F(n) = F(n - 1) + F(n - 2)~ với ~(3 \le n)~

Đề bài: Cho ~2~ số ~L, R~. Tìm số lượng số Fibonacci trong đoạn từ ~L~ đến ~R~.

Input

• Dòng đầu chứa số nguyên ~T~ thể hiện số testcase ~(1 \le T \le 10^6)~.,
• ~T~ dòng tiếp theo mỗi dòng gồm ~2~ số nguyên dương ~L, R~ ~(L \le R \le 10^6)~.

Output

• In ra ~T~ dòng. Mỗi dòng là số lượng số Fibonacci tương ứng với testcase thứ ~T~.

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

2
1 10
2 5

Output

6
3