Peter là một người thợ cơ khí, anh ta có thể chế tạo rất nhiều loại công cụ, một trong những số đó có hai loại dao và kiếm. Để chế tạo một cái dao, Peter dùng \(2\) cây gậy và \(1\) viên kim cương; để chế tạo một thanh kiếm, Peter dành \(2\) viên kim cương và \(1\) cây gậy.

Mỗi công cụ Peter có thể trao đổi với thợ kim hoàn với giá chính xác một viên ngọc lục bảo. Peter có thể kiếm được bao nhiêu ngọc lục bảo, nếu anh ta có \(a\) gậy và \(b\) kim cương?

Input

• Dòng đầu tiên chứa một số nguyên \(t\) \(( 1\le t \le 1000)\) - số lượng trường hợp.
• Dòng duy nhất của mỗi testcase chứa hai số nguyên \(a\) và \(b\) \(( 1 \le a,b \le 10^9 )\) - số lượng gậy và số lượng kim cương, tương ứng.

Output

• Đối với mỗi trường hợp, hãy in một số nguyên - số lượng ngọc lục bảo tối đa mà Peter có thể kiếm được.

Example

Input 1

2
4 4
8 7

Output 1

2
5

Giải thích:

• Trong trường hợp thứ nhất, đổi lần 1 sẽ được 1 dao, số lượng gậy và kim cương còn lại lần lượt là 2 và 3. Đổi tiếp lần 2 sẽ được 1 kiếm, số lượng còn lại gậy và kim cương là 1 và 1.

  \(=>\) 1 dao và 1 kiếm sẽ đổi được 2 ngọc lục bảo