Description

欢畅组合决定利用寒假时间出去搞钱(๑•̀ㅂ•́)و✧！

畅畅和欢欢两个人来到了生产线上加工产品，这里总共有两类产品需要他们加工：$a$产品和$b$产品。对于$a$类产品：畅畅加工一次就可以加工完成，欢欢则需要加工两次才能完成；对于$b$类产品：欢欢加工一次就可以加工完成，畅畅则需要加工三次才能完成。畅畅和欢欢每加工一次$a$产品或$b$产品都需要消耗一分钟的时间。

现在，畅畅和欢欢需要各自同时加工$n$个产品和$m$个产品，他们会按照给出的产品队列顺序从左到右依次加工每个产品，每个产品加工完一次后就会被立马重新安放在产品队列的尾部等待下一次加工。如果一个产品被加工完成了，那么他们会将这个产品移除产品队列。此外，对于每件即将被加工产品，畅畅可以选择消耗一分钟的时间来把这件产品放到欢欢加工队列的尾部，让欢欢来帮他加工这件产品，这个操作速度会略快于欢欢的加工操作。

现在，欢欢和畅畅想要知道在$k$分钟内，他们最多能够加工完多少件产品。

Input Format

第一行输入一个正整数$T$，表示共有$T(1≤T≤10)$组测试样例。

对于每组测试样例：

第一行输入三个正整数$n，m，k(1≤n,m,k≤10^3)$，分别表示畅畅和欢欢的加工队列的产品的件数。

接着第二行和第三行分别输入一个长度为$n$和$m$的，仅字母$a$和字母$b$组成的字符串，分别表示两人的加工队列。其中，字母$a$表示$a$类产品，字母$b$表示$b$类产品。

Output Format

对于每组测试样例，输出一行，包含一个正整数，表示答案。

1
3 3 5
bba
aab

5

Hint

图中黑色字母表示还没有加工过的产品，红色字母表示被加工过一次的产品，蓝色字母表示被加工过两次的产品。

Source

1816 Online Judge 10.100.0.232