Cho dãy số gồm ~n~ ~(n \le 10^5)~ phần tử nguyên dương ~a_1, a_2, ... , a_n~ ~(a_i \le 10^6)~ và một số nguyên dương ~k~ cho trước ~(k \le 10^9)~

Tìm dãy con liên tiếp dài nhất có tổng đúng bằng ~k~

Input

• Dòng đầu nhập số nguyên dương ~n~ và ~k~.
• Dòng thứ ~2~ nhập ~n~ số nguyên ~a_1, a_2, ... , a_n~.

Output

• In ra kết quả là độ dài dãy con thỏa mãn yêu cầu

Sample test

Input

7 7 
4 3 2 1 1 1 6

Output

4

Cho mảng ~a~ có ~n~ phần tử số nguyên không âm, một đoạn con liên tiếp ~a[l, r]~ được gọi là funny nếu:

• ~r - l + 1~ chẵn.
• Gọi ~mid = \frac{l + r - 1}{2}~, ~a_l \oplus a_{l + 1} \oplus ... \oplus a_{mid} = a_{mid + 1} \oplus a_{mid + 2} \oplus ... \oplus a_r~.

Hãy đếm số lượng đoạn con funny!

Input

• Dòng đầu tiên gồm số tự nhiên ~n \le 10^5~.
• Dòng tiếp theo gồm ~n~ phần tử của mảng ~a~ ~(0 \le a_i \le 10^9)~.

Output

• Số lượng dãy con funny.

Sample Test

Input

6
3 2 2 3 7 6

Output

3

Hôm nay 3 nàng tiên ánh sáng đi tìm kho báu. Khi đến trước cửa hang động, họ nhìn thấy ~n~ cây nấm với màu sắc và kích cỡ khác nhau. Theo như truyền thuyết muốn mở cánh cửa hang động thì cần sắp xếp các cây nấm này theo thứ tự tăng dần của kích cỡ, chỉ được đổi chỗ 2 cây nấm ở cạnh nhau. Mỗi lần đổi chỗ 2 cây nấm cho nhau sẽ tốn 1 ma lực, nhưng nếu 2 cây nấm cùng màu thì không tốn chút sức nào cả.

Hãy giúp Sunny Milk và đồng bọn tính số ma lực tối thiểu để có thể mở cánh cửa hang động nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~n \le 10^5~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le c_i \le n~ là màu của cây nấm thứ ~i~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le s_i \le n~ là kích cỡ của cây nấm thứ ~i~.

Output

• In ra một số nguyên duy nhất là lượng ma lực tối thiểu cần để mở cánh cửa.

Sample Test

Input:

5
1 5 2 2 1
3 2 1 2 1

Output:

6

Định nghĩa ~f(x)~ là tổng các chữ số của số nguyên ~x~. Cho số nguyên ~k~, hãy tìm giá trị ~f(x)~ nhỏ nhất có thể khi xét các số nguyên dương ~x~ chia hết cho ~k~.

Input

• Gồm một số nguyên ~2 \le k \le 100000~.

Output

• In ra giá trị ~f(x)~ nhỏ nhất.

Sample Test

Input:

6

Output:

3

Cho một số ~a~ và ~b~. Ta tiến hành xây dựng số mới ~c~ bằng cách sử dụng lần lượt các chữ số của số số ~a~ từ trái sang phải. Ở mỗi lượt có thể chọn 2 bên trái hoặc phải số ~c~ (trừ lượt đầu tiên) để đặt chữ số hiện tại vào. Ví dụ số ~c~ đang là ~38182~, đang xét số ~1~ thì sau khi đặt vào bên trái sẽ trở thành ~138182~, tương tự bên phải sẽ là ~381821~. Số ~c~ mới được phép có số 0 xuất hiện ở đầu.

Số được gọi là đẹp nếu số đó không vượt quá số ~b~. Hãy tính tổng các số đẹp được xây dựng theo cách trên, 2 số được gọi là khác nhau nếu cách xây dựng số đấy khác nhau, kể cả giá trị có bằng nhau.

Input

• Dòng đầu tiên gồm số tự nhiên ~T \le 50~ là số lượng test.
• Mỗi nhóm dòng tiếp theo gồm xâu ~a~ với ~|a| \le 500~ chỉ gồm các chữ số là số tự nhiên ~b \le 10^{500}~.

Output

• Với mỗi test in ra một số là tổng các số đẹp modulo ~10^9+7~.

Sample Test

Input:

1
1013
3000

Output:

3242