题目限制

1000 ms 128 M

题目描述

两只狗在大街上发现了T大块肉。狐狸跑过来想帮它们分肉，可有了上次被坑的经历，两只狗拒绝它，选择自己分。
对于每一块肉，甲狗和乙狗把肉一扯开，甲狗会得n千克的肉，乙狗得m千克的肉，少肉的那条狗会抢对方的肉，使自己的肉多一倍。抢了k次后两条狗都累了，那么此时少肉的一方剩下多少千克的肉呢？（注：若两狗的肉一样多，甲狗会主动抢乙狗的肉）

输入格式

第一行一个整数T，表示有T块肉
接下来T行，每行四个整数n,m,k。

输出格式

T行，每行一个答案

数据范围

对于30%的数据，k≤100000；
对于60%的数据，n,m≤100000；
对于100%的数据，n,m,k≤10^9，T≤10；

输入样例

1
5 5 3

输出样例

0

样例解释

第一次行动时，甲狗拿走乙狗的肉5千克，行动后甲狗有10千克肉，乙狗有0千克肉。 第二次和第三次行动都是乙狗拿走甲狗的肉，但是因为他没有肉，所以拿不走甲狗的肉。 最终甲狗有10千克肉，乙狗有0千克肉。