话说T^T发动了叛乱，然而他没有想到Home_Z早已看破，然而Home_Z不忍FJUT_ACM失去像T^T这样有能力的大才，更不愿意FJUT_ACM组织衰败下去，于是和T^T合谋，共享利害，同流合污。T^T提出由自己管理FJUT_ACM，而Home_Z则退居幕后，Home_Z被迫答应了。
而T^T为了巩固政权，在FJUT秘密修炼。
T^T不是做一天和尚撞一天钟的人，训练是有计划的。
他有一个能力值p。能力分为至善之力和至恶之力。
每天有两种训练方式
刚开始时训练方向为至善
A训练方式能使得能力向当前方向前进1。即如果当前能力和方向相同，则能力增强1；能力和方向相反，则能力减1。
B训练方式能改变今后的训练方向。
但是T^T发现有人暗中秘密监视他，于是他决定不按原计划进行修炼了，必须要修改其中的m天的计划，A变成B，B变成A。(同一天的计划可以被改变多次)
训练结束后，或许T^T获得至善之力，成为大善人，帮助FJUT_ACM成员脱离苦海，或者成为大恶人，更加剥削FJUT_ACM成员。
但是对于T^T来说，他只崇尚获取力量，对善恶并无所谓。
T^T只想知道如何修改计划可以使得最后获取的力量最大（无论最终是至善之力还是至恶之力）。
多组测试数据
每组测试数据第一行是一个n（1<=n<=100），表示T^T训练的天数。
第二行是一个长度为n的字符串，仅由AB组成，第i个字母表示第i天T^T的训练计划。然后是一个数字m（1<=m<=50）意义如上所述。
每个测试数据输出“Case #x: A”。x表示当前是第几组测试数据，A表示T^T训练结束后能获得的最大力量的值。
7 AAABAAA 2 2 AB 1
Case #1: 6 Case #2: 2提示： 第一组数据有2种方式修改： 1、修改第1天和第4天的计划，变成BAAAAAA，最终能力为至恶6 2、修改第4天和最后一天的计划，变成AAAAAAB，最终能力为至善6