你和cgy正在玩一个游戏，该游戏有一个 n × m 的网格，cgy会选择其中一个单元格 (x,y)，称为隐藏单元格，而你的任务则是确定该单元格的位置。

为此，你可以选择 k个单元格 (x₁,y₁),（x₂,y₂),...,（x_k,y_k),并将它们交给cgy。cgy会给你 k个数字 b₁,b₂,...,b_k,其中 b_i 是 (x_i,y_i) 到隐藏单元格 (x,y) 的曼哈顿距离。

在收到这 k 个数字后，你必须能够确定隐藏单元格在哪里，请问请问你最少可以选择多少个单元格，无论cgy选择哪个单元格个你都可以确定它的位置。

请注意,(a₁,b₁)和(a₂,b₂)单元格之间的曼哈顿距离等于 |a₁-a₂|+|b₁-b₂|。

输入的第一行包含一个整数 t (1 ≤ t ≤ 104) - 测试用例的数量。

每个测试用例单独一行，包含两个整数 n 和 m (1 ≤ n,m ≤ 109),;代表网格的大小。

每个测试用例输出一行，表示该测试用例满足题意的最小的 k 值。