Blackops学长刷题之余去超市想买点饮料喝，发现超市正在做活动，超市的饮料货架是从上到下从左到右一行行地摆好的，上面每一个位置都有一瓶饮料，而每一瓶饮料都有对应的美味值，超市负责人说为了不亏本，每一行饮料只能从左到右地按顺序拿取，比如你想拿第三行的第三个饮料，那么你必须拿第三行的第一、第二个饮料才行，但是机会总是珍贵的，老板只能允许你最多拿他给定的瓶数。那么为了获取最多的美味值而更好地投入刷题活动，可以获取的最大美味值是多少呢？

第一行一个正整数T，表示有T组输入数据
第二行三个整数n,m,k(1<=n,m<=200, 0<=k<=40000)，表示饮料货架有n行，m列，老板最多让你拿k瓶饮料

输出一个整数，表示最多可以得到的美味值。