#1120 Subsequence2

43  1 s   128 MB  

Description

N개의 원소로 이루어진 Sequence S가 주어질 때 Sequence의 연속된 원소들의 합으로 S보다 크거나 같은 수를 만들려한다. S보다 크거나 같은 수를 만들기 위해 필요한 최소한의 원소의 개수를 구하는 프로그램을 작성한다.

 

Input

Test Case T가 주어진다. 그 후 각 Test Case에 대해 한 줄에 Sequence의 원소의 개수 N(10 < N < 105) S( S < 108)가 빈 칸을 구분으로 입력된다. 그 다음 줄에 N개의 Sequence의 원소가 빈 칸을 구분으로 한 줄에 입력된다.

 

Output

Test Case에 대해 필요한 최소의 원소개수를 출력한다. 답이 존재하지 않을 경우 0을 출력한다.

 

Sample Input

Sample Output

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
2
3

Source

PKU 3061