题目描述

"今后，我们来度过满是愉快之事的人生吧~" 奈绪跟恢复了记忆的有宇成为了恋人，有一天，奈绪闲着无聊，研究起了手机上应用的图标大小，手机屏幕大小为 $5×3$ 的网格，即五行三列。

有 $x$ 个应用程序的图标大小为 $1×1$ 个单元格，这样的图标只占屏幕的一个单元格，也有 $y$ 个应用程序的图标大小为 $2×2$ 个单元格，这样的图标在屏幕上占据 $4$ 个单元格。每个屏幕的每个单元格最多只能有一个图标。

奈绪希望在最少的屏幕上放置应用程序图标。请帮她找出所需的最少屏幕数。

输入格式

第一行一个正整数 $T$（$1\le T \le 10^4$），代表测试样例的组数。

对于每个测试样例，每行有两个变量 $x$ ，$y$ （ $0\le x，y\le99$ ） ，分别代表图标大小为 $1×1$ 和 $2×2$ 的应用程序。

输出格式

输出 $T$ 行，每行一个正整数表示所需的最少屏幕数。

输入样例

11
1 1
7 2
12 4
0 3
1 0
8 1
0 0
2 0
15 0
8 2
0 9

输出样例

1
1
2
2
1
1
0
1
1
2
5

提示

蓝色代表未被占用的图标，绿色代表 $1\times1$ 的图标，红色代表 $2\times2$ 的图标。

对于第一个样例：

对于第三个样例：