一些勇敢的战士来到了一个失落的村庄。他们非常幸运，发现了很多宝藏和一个巨大的宝箱，但同时也遇到了愤怒的僵尸。

战士们非常勇敢，决定击败僵尸并将所有宝藏带回。一场残酷而漫长的战斗从早持续到晚，战士们发现这些僵尸是不死且无敌的。

当然，宝藏不能留在这里。不幸的是，由于宝箱容量的限制，战士们无法带走所有的宝藏。事实上，宝藏只有两种类型：绿宝石和蓝宝石。所有的绿宝石大小和价值都相同，且数量无限。蓝宝石也是如此。

作为拥有魔法神器“计算机”的战士祭司，给定宝箱的大小以及每种宝石的价值和大小，你需要计算出战士们能够带回的宝藏的最大总价值。

输入格式

输入包含多组测试数据。第一行给出一个整数 $T$ ($T \le 200$)，表示测试数据的组数。对于每组测试数据，只有一行，包含五个整数 $N, S_1, V_1, S_2, V_2$，分别表示宝箱的大小 $N$，绿宝石的大小 $S_1$ 和价值 $V_1$，以及蓝宝石的大小 $S_2$ 和价值 $V_2$。所有整数均为正整数，且在 32 位有符号整数范围内。

输出格式

对于每组测试数据，输出一行，包含测试用例编号和战士们能够带回的宝藏的最大总价值。

样例

样例输入 1

2
100 1 1 2 2
100 34 34 5 3

样例输出 1

Case #1: 100
Case #2: 86