题目描述

red 最近在减肥，他的朋友 A 和朋友 B 参与了他的减肥计划。但是只是陪 red 减肥实在太无聊了， A 和 B 决定在这个过程中玩一个新游戏。

游戏分为t轮，每轮开始前 A 和 B 会选定一个新的 $n \times m$ 的操场作为游戏场地。

接下来他们会让 red 在操场左下角做出预备，A 和 B 会轮流发出指令，让 red 向右跑一段距离或者向上跑一段距离。为了让游戏更加有趣，A 和 B 约定只能操控 red 跑奇数步。谁无法继续操纵 red 跑步，谁就输了，另一个人就赢得了本轮游戏。

A 先手，双方轮流操作。A 非常想赢得比赛，所以他要问你，在 $t$ 轮游戏中他能赢多少次。（假设 A 和 B 都是操纵red的高手，总是采取最优策略）。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示游戏的轮数。接下来$t$ 行，每行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^9$），表示这一轮操场的大小。

输出格式

输出一行，表示 A 胜利的次数。

输入输出

6
1 1
1 4
5 6
2 2
6 3
999999999 1000000000

4

说明/提示

在第一个样例中，red 无法移动，因此 A 输了, B 获胜。

在第二个样例中，A 可以让 red 向右移动 $3$ 格，此后 B 无法再令 red 移动，因此 B 输了, A 获胜。

对于 20% 的数据， $$ t = 1 $$。

对于另外 30% 的数据，$$ n $$ 和 $$ m $$ 在 $$ 10 $$以内。