老虎机

“在赌场里，基本原则就是让他们玩下去以及让他们再来玩。他们玩得越久，他们会输的越多，最后，我们会得到一切。”
（摘自1995年的电影Casino）

你正在一家赌场的老虎机面前，你的手上共有$k$个游戏币。

当你每次按下老虎机的按钮时，它会随机地报出一个数字$d$，如果$d=0$，那么什么事情都不会发生；如果$d>0$，那么恭喜你，老虎机会吐给你$d$个游戏币；但是如果$d<0$，很不幸，你将需要支付给老虎机$-d$个游戏币。

这台老虎机的工作原理很简单，在老虎机内部有一个长度为$n$的序列$a[0],a[1],\dots,a[n-1]$，每当你按下按钮时，如果你手上共有$k$个游戏币，那么它报出的数字$d$就是$a[k\bmod n]$。

前几次赌博让你尝到了甜头，贪婪的欲望驱动着你不停地按下老虎机的按钮。当$d<0$且你支付不了那么多游戏币时，你宣告破产。请问在你破产的时候你一共按过多少次按钮呢？

第一行包含一个正整数$T(1\leq T\leq 5000)$，表示测试数据的组数。

每组数据第一行包含两个正整数$n,k(1\leq n\leq 100000,1\leq k\leq 10^{18})$，表示序列长度以及你初始的游戏币数量。

第二行包含$n$个整数$a[0],a[1],\dots,a[n-1](-10^9\leq a[i]\leq 10^9)$。

输入数据保证所有数据中$n$的总和不超过$1000000$。

对于每组数据输出一行一个整数，即你破产的时候你一共按过按钮的次数。如果你运气很好，永远都不会破产，请输出$-1$。

1
5 20
-1 -2 3 4 -5

5

Claris

Championship