The USA Construction Operation (USACO) recently ordered Farmer John to arrange a row of n haybale piles on the farm. The i-th pile contains a_i haybales. 

However, Farmer John has just left for vacation, leaving Bessie all on her own. Every day, Bessie the naughty cow can choose to move one haybale in any pile to an adjacent pile. Formally, in one day she can choose any two indices i and j (1 ≤ i, j ≤ n) such that |i-j|=1 and a_i>0 and apply a_i = a_i - 1, a_j = a_j + 1. She may also decide to not do anything on some days because she is lazy.

Bessie wants to maximize the number of haybales in pile 1 (i.e. to maximize a_1), and she only has d days to do so before Farmer John returns. Help her find the maximum number of haybales that may be in pile 1 if she acts optimally!

Input

The input consists of multiple test cases. The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases. Next 2t lines contain a description of test cases — two lines per test case.

The first line of each test case contains integers n and d (1 ≤ n,d ≤ 100) — the number of haybale piles and the number of days, respectively. 

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 100) — the number of haybales in each pile.

Output

For each test case, output one integer: the maximum number of haybales that may be in pile 1 after d days if Bessie acts optimally.

Example

Input


3
4 5
1 0 3 2
2 2
100 1
1 8
0


Output


3
101
0

Note

In the first test case of the sample, this is one possible way Bessie can end up with 3 haybales in pile 1: 

  * On day one, move a haybale from pile 3 to pile 2 
  * On day two, move a haybale from pile 3 to pile 2 
  * On day three, move a haybale from pile 2 to pile 1 
  * On day four, move a haybale from pile 2 to pile 1 
  * On day five, do nothing 



In the second test case of the sample, Bessie can do nothing on the first day and move a haybale from pile 2 to pile 1 on the second day.
import javax.swing.tree.TreeCellRenderer;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        new Main().run();}

    int n;
    int v[][];
    int lisan(int[][] arr,int idx){
        for(int i=0;i<n;++i){
            v[i][0] = arr[i][idx];
            v[i][1] = i;
        }
        Arrays.sort(v, new Comparator<int[]>() {
            @Override
            public int compare(int[] x, int[] y) {
                return x[0]-y[0];
            }
        });
        int tot = -1;
        for (int i = 0; i < n; ++i) {
            if(i==0||v[i][0]!=v[i-1][0]) tot++;
            arr[v[i][1]][idx] = tot;
        }
        // id range from 0 to tot
        return tot+1;
    }


    long inv(long a, long MOD) {
        //return fpow(a, MOD-2, MOD);
        return a==1?1:(long )(MOD-MOD/a)*inv(MOD%a, MOD)%MOD;
    }

    // 计算某个特别大的组合数
    long C(long n,long m, long MOD) {
        if(m+m>n)m=n-m;
        long up=1,down=1;
        for(long i=0;i<m;i++)
        {
            up=up*(n-i)%MOD;
            down=down*(i+1)%MOD;
        }
        return up*inv(down, MOD)%MOD;
    }

    long[][] mult(long a[][],long b[][], long mod){
        int l1 = a.length;
        int l2 = b.length;
        int l3 = b[0].length;
        long r[][] = new long[l1][l3];
        for(int i=0;i<l1;++i){
            for(int j=0;j<l2;++j){
                for(int k=0;k<l3;++k){
                    r[i][k] = (r[i][k] + a[i][j] * b[j][k])%mod;
                }
            }
        }
        return r;
    }

    long[][] ones(int len){
        long r[][] = new long[len][len];
        for(int i=0;i<len;++i){
            r[i][i] = 1L;
        }
        return r;
    }

    long[][] quick(long a[][], long times,long mod){
        int len = a.length;
        long ans[][] = ones(len);

        while(times>0){
            if((times&1)==1) {
                ans = mult(ans, a, mod);
            }
            a = mult(a, a, mod);
            times >>= 1;
        }

        return ans;
    }


    int sg(int x,int y){

        int v = (x-1)|(y-1);

        for(int i=0;;i++){
            if((v&(1<<i))==0){
                return i;
            }
        }

    }

    int time(int i,int j,int b[]){
        if(i==0) return 0;
        return b[i]^b[j];
    }

    static long p = 0;
    void solve() {
//        int c = ni();
//        for(int i=0;i<c;++i){
//            int n  = ni();
//            int []b = new int[n+1];
//            int []r = new int[n+1];
//
//            for(int j=1;j<=n;++j){
//                b[j] = ni();
//                r[j] = ni();
//            }
//
//            int dp[][][] = new int[n+1][1<<8][16];
//
//            for(int j=0;j<=n;++j){
//                for(int st=0;st<1<<8;++st) {
//                    for (int k = -8; k <= 7; ++k) {
//                        dp[j][st][k+8] = 1000000000;
//                    }
//                }
//            }
//            dp[1][0][7] = 0;
//            for(int j=1;j<=n;++j){
//                for(int st=0;st<1<<8;++st){
//                    for(int k=Math.max(-j,-8);k<=7&&j+k<=n;++k){
//                        int kk = k+8;
//                        if((st&1)>0){
//                            if(j+1<=n&&kk-1>=0) {
//                                dp[j + 1][st >> 1][kk - 1] = Math.min(dp[j + 1][st >> 1][kk - 1], dp[j][st][kk]);
//                            }
//                        }else{
//                            int cnt = 0;
//                            for(int l=7;l>=0;--l) {
//                                if(j+l>n) continue;
//                                if((st&(1<<l))==0){
//                                    boolean ok = true;
//                                    int add = 0;
//                                    for(int g=l-1;g>=0;--g){
//                                        if((st&(1<<g))>0){
//                                            add++;
//                                        }else if(r[j+g]<cnt+add+1){
//                                            ok = false;break;
//                                        }
//                                    }
//                                    if(ok) {
//                                        dp[j][st|(1<<l)][l+8] = Math.min(dp[j][st][kk] + time(j+k,j+l, b), dp[j][st|(1<<l)][l+8]);
//                                    }
//                                }else{
//                                    cnt++;
//                                }
//                            }
//                        }
//                    }
//                }
//            }
//            int an = 0;
//            for(int st=0;st<1<<8;++st) {
//                for (int k = -8; k <= 7; ++k) {
//                    an = Math.min(an,dp[n][st][k+8]);
//                }
//            }
//            println(an);
//
//
//        }

        for(int i=ni();i>0;--i){
            int n  = ni();
            int d  = ni();
            int a[] = na(n);
            int s = a[0];
            for(int j=1;j<n&&d>0;++j){
                int take = Math.min(d / (j ), a[j]);
                d -= take*(j);
                s += take;
            }
            println(s);

        }


//            int n = ni();
//
//            for(int i=0;i<n;++i){
//                char c =nc();
//                if(c=='A'){
//
//                }
//            }









//        for(int i=500;i>=100;--i){
//            if(good(i)!=bad(i)){
//                println(good(i));
//                println(bad(i));
//                println(i);
//                println("-----------------------");
//            }
//        }





































        //N , M , K , a , b , c , d . 其中N , M是矩阵的行列数；K 是上锁的房间数目，(a, b)是起始位置，(c, d)是出口位置


//        int n = ni();
//        int m = ni();
//        int k = ni();
//        int a = ni();
//        int b = ni();
//        int c = ni();
//        int d = ni();
//
//
//        char cc[][] = nm(n,m);
//        char keys[][] = new char[n][m];
//
//        char ky = 'a';
//        for(int i=0;i<k;++i){
//            int x = ni();
//            int y = ni();
//            keys[x][y] = ky;
//            ky++;
//        }
//        int f1[] = {a,b,0};
//
//        int dd[][] = {{0,1},{0,-1},{1,0},{-1,0}};
//
//        Queue<int[]> q =  new LinkedList<>();
//        q.offer(f1);
//        int ts = 1;
//
//        boolean vis[][][] = new boolean[n][m][33];
//
//        while(q.size()>0){
//            int sz = q.size();
//            while(sz-->0) {
//                int cur[] = q.poll();
//                vis[cur[0]][cur[1]][cur[2]] = true;
//
//                int x = cur[0];
//                int y = cur[1];
//
//                for (int u[] : dd) {
//                       int lx = x +  u[0];
//                       int ly = y +  u[1];
//                       if (lx >= 0 && ly >= 0 && lx < n && ly < m && (cc[lx][ly] != '#')&&!vis[lx][ly][cur[2]]){
//                            char ck =cc[lx][ly];
//                            if(ck=='.'){
//                                if(lx==c&&ly==d){
//                                    println(ts); return;
//                                }
//                                if(keys[lx][ly]>='a'&&keys[lx][ly]<='z') {
//                                    int cao = cur[2] | (1 << (keys[lx][ly] - 'a'));
//                                    q.offer(new int[]{lx, ly, cao});
//                                    vis[lx][ly][cao] = true;
//                                }else {
//
//                                    q.offer(new int[]{lx, ly, cur[2]});
//                                }
//
//                            }else if(ck>='A'&&ck<='Z'){
//                                int g = 1<<(ck-'A');
//                                if((g&cur[2])>0){
//                                    if(lx==c&&ly==d){
//                                        println(ts); return;
//                                    }
//                                    if(keys[lx][ly]>='a'&&keys[lx][ly]<='z') {
//
//                                        int cao = cur[2] | (1 << (keys[lx][ly] - 'a'));
//                                        q.offer(new int[]{lx, ly, cao});
//                                        vis[lx][ly][cao] = true;;
//                                    }else {
//
//                                        q.offer(new int[]{lx, ly, cur[2]});
//                                    }
//                                }
//                            }
//                       }
//                }
//
//                }
//            ts++;
//        }
//        println(-1);




//        int n = ni();
//
//        HashSet<String> st = new HashSet<>();
//        HashMap<String,Integer> mp = new HashMap<>();
//
//
//        for(int i=0;i<n;++i){
//            String s  = ns();
//            int id= 1;
//            if(mp.containsKey(s)){
//                int u = mp.get(s);
//                id = u;
//
//            }
//
//            if(st.contains(s)) {
//
//                while (true) {
//                    String ts = s + id;
//                    if (!st.contains(ts)) {
//                        s = ts;
//                        break;
//                    }
//                    id++;
//                }
//                mp.put(s,id+1);
//            }else{
//                mp.put(s,1);
//            }
//            println(s);
//            st.add(s);
//
//        }

//        int t = ni();
//
//        for(int i=0;i<t;++i){
//            int n = ni();
//            long w[] = nal(n);
//
//            Map<Long,Long> mp = new HashMap<>();
//            PriorityQueue<long[]> q =new PriorityQueue<>((xx,xy)->{return Long.compare(xx[0],xy[0]);});
//
//            for(int j=0;j<n;++j){
//                q.offer(new long[]{w[j],0});
//                mp.put(w[j],mp.getOrDefault(w[j],0L)+1L);
//            }
//
//            while(q.size()>=2){
//                long f[] = q.poll();
//                long y1 = f[1];
//                if(y1==0){
//                    y1 = mp.get(f[0]);
//                    if(y1==1){
//                        mp.remove(f[0]);
//                    }else{
//                        mp.put(f[0],y1-1);
//                    }
//                }
//                long g[] = q.poll();
//                long y2 = g[1];
//                if(y2==0){
//                    y2 = mp.get(g[0]);
//                    if(y2==1){
//                        mp.remove(g[0]);
//                    }else{
//                        mp.put(g[0],y2-1);
//                    }
//                }
//                q.offer(new long[]{f[0]+g[0],2L*y1*y2});
//
//            }
//            long r[] = q.poll();
//            println(r[1]);
//
//
//
//
//        }
        //  int o= 9*8*7*6;
        //  println(o);


//       int t = ni();
//       for(int i=0;i<t;++i){
//           long a = nl();
//           int k  = ni();
//           if(k==1){
//               println(a);
//               continue;
//           }
//
//           int f = (int)(a%10L);
//           int s = 1;
//           int j = 0;
//           for(;j<30;j+=2){
//               int u = f-j;
//               if(u<0){
//                   u = 10+u;
//               }
//               s = u*s;
//               s = s%10;
//               if(s==k){
//                   break;
//               }
//           }
//
//           if(s==k) {
//               println(a - j - 2);
//           }else{
//               println(-1);
//           }
//
//
//
//
//       }

//     int m = ni();
//     h = new int[n];
//     to = new int[2*(n-1)];
//     ne = new int[2*(n-1)];
//     wt = new int[2*(n-1)];
//
//     for(int i=0;i<n-1;++i){
//         int u = ni()-1;
//         int v = ni()-1;
//
//     }
        //  long a[] = nal(n);


//        int n = ni();
//        int k = ni();
//        t1 = new long[200002];
//
//        int p[][] = new int[n][3];
//
//        for(int i=0;i<n;++i){
//            p[i][0]  = ni();
//            p[i][1]  = ni();
//            p[i][2]  = i+1;
//        }
//        Arrays.sort(p, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] x, int[] y) {
//                if(x[1]!=y[1]){
//                    return Integer.compare(x[1],y[1]);
//                }
//                return Integer.compare(y[0], x[0]);
//            }
//        });
//
//        for(int i=0;i<n;++i){
//            int ck = p[i][0];
//
//        }

















    }









//    int []h,to,ne,wt;


    //    long t2[];
    void update(long[] t,int i,long v){
        for(;i<t.length;i+=(i&-i)){
            t[i] += v;
        }
    }
    long get(long[] t,int i){
        long s = 0;
        for(;i>0;i-=(i&-i)){
            s += t[i];

        }
        return s;
    }

    int equal_bigger(long t[],long v){
        int s=0,p=0;
        for(int i=Integer.numberOfTrailingZeros(Integer.highestOneBit(t.length));i>=0;--i) {
            if(p+(1<<i)< t.length && s + t[p+(1<<i)] < v){
                v -= t[p+(1<<i)];
                p |= 1<<i;
            }
        }
        return p+1;
    }

    static class S{
        int l = 0;
        int r = 0 ;
        long tot = 0;
        long plus = 0;
        long multi = 1;


        public S(int l,int r) {
            this.l = l;
            this.r = r;
        }
    }

    static S a[];
    static long[] o;

    static void init(long[] f){
        o = f;
        int len = o.length;
        a = new S[len*4];
        build(1,0,len-1);
    }

    static void build(int num,int l,int r){
        S cur = new S(l,r);
        if(l==r){
            a[num] = cur;
            a[num].tot = o[l];
          //  a[num].tot %= p;
            return;
        }else{
            int m = (l+r)>>1;
            int le = num<<1;
            int ri = le|1;
            build(le, l,m);
            build(ri, m+1,r);
            a[num] = cur;
            pushup(num,le,ri);
         }
    }

    static long query(int num,int l,int r){
        if(a[num].l>=l&&a[num].r<=r){
          //   a[num].tot %= p;
            return a[num].tot;
        }else{
            int m = (a[num].l+a[num].r)>>1;
            int le = num<<1;
            int ri = le|1;
         //   pushdown(num, le, ri);
            long res = Long.MIN_VALUE;
            if(l<=m) {
                res = Math.max(res, query(le, l, r));
            }
            if(r>m){
                res = Math.max(res, query(ri, l, r));
            }
          //  pushup(num,le,ri);
            return res;
        }
    }

    static void update(int num,int l,long v){
        if(a[num].l == a[num].r){
            a[num].tot  = v;
        }else{
            int m = (a[num].l+a[num].r)>>1;
            int le = num<<1;
            int ri = le|1;
           // pushdown(num, le, ri);
            if(l<=m){
                update(le, l, v);
            }
            if(l>m){
                update(ri, l, v);
            }
            pushup(num,le,ri);
        }
    }


    static void update1(int num,int l,int r,long v){
        if(a[num].l>=l && a[num].r<=r){
            a[num].tot += v*(a[num].r-a[num].l+1);
            a[num].tot %= p;
            a[num].plus += v;
            a[num].plus %= p;
        }else{
            int m = (a[num].l+a[num].r)>>1;
            int le = num<<1;
            int ri = le|1;
            pushdown(num, le, ri);
            if(l<=m){
                update1(le, l, r, v);
            }
            if(r>m){
                update1(ri, l, r, v);
            }
            pushup(num,le,ri);
        }
    }

    static void update2(int num,int l,int r,long v){
        if(a[num].l>=l && a[num].r<=r){
            a[num].tot *= v;
            a[num].tot %= p;
            a[num].plus *= v;
            a[num].plus %= p;
            a[num].multi *= v;
            a[num].multi %= p;
        }else{
            int m = (a[num].l+a[num].r)>>1;
            int le = num<<1;
            int ri = le|1;
            pushdown(num, le, ri);
            if(l<=m){
                update2(le, l, r, v);
            }
            if(r>m){
                update2(ri, l, r, v);
            }
            pushup(num,le,ri);
        }
    }

    static void pushup(int num,int le,int ri){
        a[num].tot = Math.max(a[le].tot , a[ri].tot);
    }

    static void pushdown(int num,int le,int ri){
        if(a[num].multi!=1) {
            a[le].tot *= a[num].multi;
            a[le].tot %= p;
            a[ri].tot *= a[num].multi;
            a[ri].tot %= p;
            a[le].multi *= a[num].multi;
            a[ri].multi *= a[num].multi;
            a[le].multi %= p;
            a[ri].multi %= p;
            a[le].plus *= a[num].multi;
            a[ri].plus *= a[num].multi;
            a[le].plus %= p;
            a[ri].plus %= p;
            a[num].multi = 1;
        }
        if(a[num].plus!=0) {
            a[le].tot += (a[le].r-a[le].l+1)*a[num].plus;
            a[ri].tot += (a[ri].r-a[ri].l+1)*a[num].plus;
            a[le].tot %= p;
            a[ri].tot %= p;
            a[le].plus += a[num].plus;
            a[ri].plus += a[num].plus;
            a[le].plus %= p;
            a[ri].plus %= p;
            a[num].plus = 0;
        }
    }

    long gcd(long a,long b){ return b==0?a: gcd(b,a%b);}
    int gcd(int a,int b){ return b==0?a: gcd(b,a%b);}
    InputStream is;PrintWriter out;
    void run() throws Exception {is = System.in;
        // is  = new FileInputStream("C:\\Users\\Luqi\\Downloads\\P1273_2.in");
        out = new PrintWriter(System.out);solve();out.flush();}
    private byte[] inbuf = new byte[2];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {lenbuf = is.read(inbuf);} catch (IOException e) {throw new InputMismatchException();}
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];}
    private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}
    private int skip() {int b;while((b = readByte()) != -1 && isSpaceChar(b));return b;}
    private double nd() {return Double.parseDouble(ns());}
    private char nc() {return (char) skip();}
    private char ncc() {int b;while((b = readByte()) != -1 && !(b >= 32 && b <= 126));return (char)b;}
    private String ns() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[] ns(int n) {char[] buf = new char[n];int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b;b = readByte(); }
        return n == p ? buf : Arrays.copyOf(buf, p);}
    private String nline() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') { sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[][] nm(int n, int m) {char[][] a = new char[n][];for (int i = 0; i < n; i++) a[i] = ns(m);return a;}
    private int[] na(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = ni();return a;}
    private long[] nal(int n) { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nl();return a;}
    private int ni() { int num = 0, b; boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private long nl() { long num = 0; int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9')  num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    void print(Object obj){out.print(obj);}
    void println(Object obj){out.println(obj);}
    void println(){out.println();}
}