你能体谅 我有雨天

偶尔胆怯 你都了解

过去那些大雨落下的瞬间

我突然发现

谁能体谅 我的雨天

所以情愿回你身边

此刻脚步 会慢一些

如此坚决

你却越来越远

——孙燕姿《雨天》

你的心情会随天气改变吗？很多人每当下雨时心情就会变的特别惆怅，你是吗？如果你是一个随着天气变化而改变心情的人，那么提前了解未来的天气状况或许是一个很好的调节心情的方法呢。

同样的，小应同学也是这样一个会随着天气变化而改变心情的孩子，那么他就非常想知道未来的天气状况。

已知昨天和今天的天气情况，如果连续两天都下雨的话，那么明天下雨的概率是a；如果今天下雨昨天没下雨的话，那么明天下雨的概率是b；如果今天没下雨昨天下雨的话，那么明天下雨的概率是c；如果今天和昨天都没下雨的话，那么明天下雨的概率是d，现在小应同学想知道N天后（指的是今天之后的第N天，明天就是第1天）的天气情况，那么请问N天后下雨的概率是多少？

每个输入文件的第一行是测试数据的组数cas；

接下来就是1-cas组的测试数据。

每一组测试数据包括3行：

第一行是昨天和今天的天气情况x和y，其中x，y只有0和1两种情况，0代表不下雨，1代表下雨；

第二行是4个非负的数据a，b，c，d，（≤1）；

第三行是N，（N∈[1,2³⁰]）。

每组数据输出一行，输出N天之后下雨的概率用百分比表示z%，z保留到整数。