Dãy con nhỏ nhất

Điểm số: 1

Giới hạn thời gian: 1s

Giới hạn bộ nhớ: 512 MB

Người đăng: ICTU

Cho mảng số nguyên dương A=(a1, a2, …, an) và một số nguyên dương S. Viết chương trình cho biết độ dài của dãy con nhỏ nhất sao cho tổng của dãy con lớn hơn hoặc bằng S. Nếu không có dãy con thì trả về giá trị là 0. Dãy con của A kí hiệu là Aij = (ai, ai+1, ai+2,…, aj), n >= i, j >= 1. Độ dài của dãy con chính là số phần tử của dãy con đó.

Input

Bao gồm 2*N+1 dòng:

Dòng 1: Chứa số nguyên dương N (1<= N <= 10). N là số lượng test case.

2*N Dòng tiếp theo là các testcase. Mỗi testcase gồm 2 dòng:

Dòng thứ 1: là hai số nguyên S (1 <= S <= 109 ) và n  (1 <= n <= 105). 

Dòng thứ 2: là các số nguyên dương trong mảng A ( 1 <= ai <= 5 x 105). Các số nguyên cách nhau bởi dấu cách

 

Output

N dòng, mỗi dòng là độ dài của dãy con.

Ví dụ:

input

output

3

7 6

2 3 1 2 4 3

4 3

1 4 4

11 8

1 1 1 1 1 1 1 1

2

1

0