有一个疯狂的化学家制造了一种新的原子病毒炸弹，它会杀死所有人。其工作原理如下：

该病毒有 $N$ 种不同的形态。每一秒，一种形态的病毒会转化为一种或多种相同或不同形态的病毒。此外，每种形态在转化的过程中会产生一定数量的氚原子。当这些原子的总数达到临界值 $L$ 时，它们就会像氢弹一样爆炸。

我们想知道从一个可怜人被感染开始，到他爆炸需要多长时间。

一个简单的例子是只有一种形态的病毒，它每一秒会转化为两个相同形态的病毒，并产生一个氚原子。假设 $L = 15$。一秒后，有两只病毒和一个原子。两秒后，有四只病毒和三个原子。三秒后，有八只病毒和七个原子。四秒后，炸弹爆炸。

让我们看一个稍微复杂的例子，病毒有两种形态 A 和 B，$L = 500$。每一秒，形态 A 的病毒会转化为三个形态 A 的病毒和一个形态 B 的病毒，并产生一个氚原子。形态 B 的病毒会转化为两个形态 B 的病毒，并产生一百个氚原子。如果我们从一个形态 A 的病毒开始，那么一秒后我们有 3 个 A，1 个 B 和 1 个原子。两秒后我们有 9 个 A，5 个 B 和 104 个原子。三秒后我们有 27 个 A，19 个 B 和 613 个原子。所以答案是三秒。

输入格式

输入的第一行给出了测试用例的数量 $T \le 100$。每个测试用例的第一行包含 $1 \le N \le 20$ 和 $1 \le L \le 1000000000$。接下来有 $N$ 行，每行对应一种形态。每种形态的描述包含 $N + 1$ 个小于 1000 的非负整数。前 $N$ 个数描述了它转化为不同形态病毒的数量，最后一个数描述了在此过程中产生的氚原子数量。

输出格式

为每个测试用例输出一行。我们假设患者最初被第一种形态的病毒感染。如果病毒炸弹永远不会爆炸，输出 “lucky”。否则，输出患者爆炸前所经过的秒数。

样例

输入格式 1

3
1 15
2 1
2 500
3 1 1
0 2 100
1 15
2 0

输出格式 1

4
3
lucky