“明天玩什么游戏好呢？”这是Mr.Lee今天要思考的事情。

“后天玩什么游戏好呢？”这是Mr.Lee明天要思考的事情。

Mr.Lee每天都在为明天玩什么游戏而发愁，他有n个游戏。

《塞尔达传说：旷野之息》，《超级马里奥奥德赛》，《星之卡比：新星同盟》，《巫师3：狂猎》，《王权的陨落》等等。

如果在某一天Mr.Lee玩了k款游戏，那么他会获得k点快乐值。

如果在某一天Mr.Lee没有玩游戏，那么他会失去p点快乐值。

现在他给每个游戏定了一个数字，如果当前的天数能被这个数字整除，那么他在今天就会玩这个游戏。

现在你要计算出Mr.Lee在m天能获得多少快乐值。

多组样例

第一行一个T(1<=T<=1000)代表样例组数

对于每组样例

第一行一个n,m,p代表游戏数，天数和数值p(1<=n<=15,1<=m<=10⁸,1<=p<=10)

接下来n个数代表每款游戏的数字(1<=a_i<2¹⁶)

对于每组样例

输出Mr.Lee的快乐值

Author  Mr.Lee