Time Limit: 1500 MS    Memory Limit: 131072 K 


Description

在奶牛们理清债务后,部分奶牛惊奇的发现,他们投资的股票、基金突然大涨,于是,他们打算去购买一个新村庄,以继续提升奶牛们的生活质量。 他们购买的新村庄是一个有爱的村庄,名字叫奶牛镇。在这个谐气慢慢的小镇上里,奶牛们的生活快乐又和谐。。。奶牛镇呈长条形状,可分为排成一行的N个小格。每个格子可能是空地, 也可能是U盘、硬盘、电脑、服务器或超级计算机中的一种物品。每种物品都有一个等级,U盘的等级是1,硬盘的等级是2,依此类推。 你,作为奶牛谐星,是这个小镇的建造者。你会陆续获得D件物品,你要将它们合理地放置在小镇的空地上。你的目标是要让小镇的总谐气尽可能大。谐气的获得规则在后面说明。 关于放置的规则有以下几条: 1.每个物品都必须放在一个地方,不能丢弃,如果没有空地了,建造直接结束; 2.物品可以放在一格空地上,或者临时放在奶牛背上。奶牛背上同时最多只能放一件物品,它一开始是空的。因为只有你这头谐星奶牛在建造,so,自然只有你一个后背能放置。 3.一旦物品放在某个空格上,只要符合条件,神奇的约翰就会自动将一些物品合成一个大的物品,这是强制被动的,也是瞬间的。直到合成结束后,才能放置下一个物品。 4.放在你背上的物品,随时可以取出放到空地上(但注意不能在合成的过程中放置),也可以一直留在你的背上(毕竟你是个谐星)。 5.除非利用你的后背,不然不能更改物品的放置顺序; 总结起来,这个建造的流程就是获得一个新物品,决定是否将这个物品放在你的背上,再决定将你背上的物品或新物品放到哪个空地上,约翰会自动判定合成,获得谐气, 直到所有物品都被放置完毕,或空地用完为止。 最后是关于合成的规则。合成是自动完成的,也是强制性的。如果有连续两个或以上相邻的格子里有相同等级的物品,它们会自动合成成一个新的物品,新物品的等级比之前高一个级别。 合成分三步: 1.确定有多少物品参与合成,这些物品的位置必须连在一起,等级相同。参与合成的物品会全部消失,对应的格子边成空地; 2.假设有A个K级物品参与合成,那么将获得A*(2^K)点人谐气。例如有一次5个U盘进行了合成,那么总谐气就会增加5*(2^1)=10; 3.一个K+1等级的物品会出现在一个格子里。如果K+1大于5,则跳过这步,但第二步中的谐气仍然要算,第一步中的旧物品也会被清除。这个高等级的物品只会出现在参与合成的格子上。 每个格子会记录最后一次被放置物品的时间,新的物品会出现在该时间最晚的那个格子里,换而言之,就是出现在最近被放置过东西的格子里; 最后,请注意合成是会触发多次的,比如两个U盘合成一个硬盘,如果这个硬盘旁边还有其他硬盘,合成将继续发生下去。 现在,给出N和获得物品的顺序及等级,请你要合理地将这些物品放置在一个初始全是空地的村子里,使得村子最终的谐气值尽可能高。当所有物品都被放置,或者村子不能再放物品了, 都会结束村子的建设,而此时村子里累计谐气值就是最终成果。

Input

第一行为case数。 对于每组数据: 第一行给出两个整数N和D,用空格隔开。N表示村庄大小,D表示物品数量。 第二行为一个字符串,每个字符为'1'..'5'之间的一个字符,表示每天你可以放置的物品的等级。

Output

输出一个整数,表示你能得到的最大的谐气值。

Sample Input

1 4 10 1132411235

Sample Output

168 hint: 3<=N<=6,D<=101