菜哭武最近得到了一套卡牌，每天都喜欢拉着自己的同事们做一些游戏。这次，他拿出了N张，上面印着整数的卡牌，上面的数字依次是a1,a2,a3……an。

他知道，从这里面取任意多张牌，一共有2N种方法，除了什么都不取的那一种，其他的可以计算出这些卡牌上面数字的和，现在他想知道，这2N-1种方法里，数字和最小的K种都是多少。希望你能帮帮他啊。

题目包含多组数据。

输入的第一行有一个整数T (1≤T≤10) 代表有T组数据。

对于每组数据分为两行：          

第一行有两个整数N，K (其中1≤N≤200000, 1≤K≤min2N-1, 200000 )，

第二行有N个整数，分别是a1,a2,a3……an (-108≤ai≤108)。

对于每组数据，输出的第一行为Case #x: ,其中x是数据编号（从1开始），

第二行输出一个非负整数，为正常需要输出的K的数字的和 Mod 99989的结果。

本题因为输出较大，在OJ评测会出现输出超限的问题，现场赛时采用了手工评测。现在已修改输出格式，请各位注意。