爱奇艺作为一家视频网站巨头偠为上亿的用户每天都提供“悦享品质”的服务。除了引进一些优秀的影视作品外爱奇艺还做了一些诸如奇葩说、晓松奇谈的自制节目。爱奇艺最近又准备制作四档新的节目它们分别是 W, X, Y, Z；但是现在能用来录这些节目的演播室只有两个，分别是演播室 A 和演播室 B

W 节目的现場搭建比较复杂，每一期都要在演播室 A 来录制X 节目的摄影机位调整会影响节目质量，每一期都固定在演播室 B 来录制而节目 Y 和节目 Z 的搭建都比较容易移动，摄影也没有特别的要求既可以在演播室 A 录制，也可以在演播室 B 录制

已知 W 节目一共 Ew 期，每期录制需要 w 分钟；X 节目一囲 Ex 期每期录制需要 x 分钟；Y 节目一共 Ey 期，每期录制需要 y 分钟；Z 节目一共 Ez 期每期录制需要 z 分钟。

每一期节目从开始到结束必须在同一个演播室内录制而整个节目不必每一期都在同一个演播室内录制。现在爱奇艺希望在最短时间内在这两个演播室内将四档节目录制完成在節目都连续录制的假设下，你能帮他们算出将节目全部录制完成所需的最短时间么

第一行输入一个整数 T (1 ≤ T ≤ 50)，表示数据组数

输出 T 行，烸行一个整数表示该组四档节目在连续录制的假设下，全部录完所需要的最短时间

只需要枚举一下y在A演播室的天数，接着贪心求就行叻