D. Magic Sticks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a n × m grid, your goal is to find a group of lines such that the following conditions are met:

  1. No two lines are touching.
  2. Each cell in the grid has one of its sides covered by at least one line in the group.

A line is a border of a cell in the grid with length 1. Each cell has 4 lines covering every side of it. Every pair of neighboring cells shares a line. Two lines are touching if they meet at their ends.

The size of a group of lines is the number of lines it contains. Your task is to find the minimum size of a group of lines that meet all the conditions above. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 128) specifying the number of test cases.

Each test case consists of a single line containing two integers n and m (1 ≤ n ≤ 109, 1 ≤ m ≤ 1024), giving a grid of size n × m.

Output

For each test case, print a single line containing the minimum size of a group of lines that meet all the conditions in the statement above.

Example
Input
1
4 4
Output
10