#225. 开机密码

开机密码

题目描述

机器人ymzs666的开机密码特别烦琐,并且在时时刻刻的改变,但是拥有以下规律:

它会提示出四个整数 abx a,b,x 和y,保证ax a≥x by b≥y

操作内容为:选择 aa 或者 bb 并将其值减少 11。(提示:你要保证每次操作之后ax a≥x by b≥y

你的任务是通过不超过 nn 次的操作,找出机器人的开机密码,这个密码就是a和b的最小可能的乘积。

需要回答t个独立的测试

输入格式

输入的第一行包含一个整数t 1t20000 (1≤t≤20000) --测试用例数。然后,t个测试数据随之而来。

测试用例的唯一一行包含五个整数 abxy a、b、x、y nn1abxyn10000000001≤a、b、x、y、n≤1000000000)。输入的附加约束条件:axa≥xbyb≥y总是成立。

输出格式

对于每个测试用例,打印一个整数:通过应用给定操作不超过n次,可以实现a和b的最小可能乘积。

样例

输入

1
10 10 8 5 3

输出

70

样例解释

a与b可能的值有{10,10},{10,9},{10,8},{10,7},{9,10},{9,9},{9,8},{8,10},{8,9}
可知当a为10,b为7时 a*b的值为70(值最小)

数据范围与提示

1<=a,b,x,y,n<=1e91 <= a,b,x,y,n <= 1e9