Description

小D的飞车已经升级完成了，但他自己是没办法同时驾驶这么高端的飞车的，所以他需要招募一些人员,（勇者的旅途总是需要一些炮灰）。

不过他的经费全部用于升级飞车了。招募人手就只能靠小D的人格魅力了，幸亏小D学过一段时间的单口相声，才让他在人才市场不显得那么格格不入。小D的第一天的就迎来了两位可能招募的伙伴:翠神和小菊。

小D准备了a+b+c+d个要讲的笑话，按类型分组:

• 类型1:翠神和小菊都喜欢；
• 类型2:翠神喜欢，小菊不喜欢；
• 类型3:小菊喜欢，翠神不喜欢；
• 类型4:翠神和小菊都不喜欢。

最初，两个观众的情绪都等于****

当观众听到自己喜欢 的笑话时，他的情绪会增加****1

当观众听到自己不喜欢 的笑话时，他的情绪会降低****1

如果观众的情绪变得消极****( 情绪小于)，他就会认为这个老板不太行，并离开。

当有人离开时，小D会感到很挫败，并结束这场表演。如果没有人离开，小D就没有笑话了，他也会结束这场表演，并招募两位人才。

因此，小D想以这样一种方式安排她的笑话，使得节目尽可能地持续。帮助她计算在节目结束前她最多能讲多少个笑话。

Format

Input

第一行：一个整数——测试用例的数量

每一个例子一行：包含四个整数）—小D准备的每种类型笑话的数量

Output

对于每个测试案例，打印一个整数——在至少一个人才离开之前或者在他讲完笑话之前，小D可以讲的最大笑话数。

Samples

4
5 0 0 0
0 0 0 5
2 5 10 6
3 0 0 7

5
2
16
8

Hint