Mall đang sở hữu vùng đất EALand được chia thành ~n \times m~ ô vuông, các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới và các cột từ ~1~ đến ~m~ từ trái sang phải, ô vuông ~(i,j)~ nằm ở vị trí hàng ~i~ và cột ~j~ có độ dài cạnh bằng ~1~.

Mall muốn xây dựng một khu vườn hình chữ nhật sao cho mỗi cạnh có độ dài nguyên dương và đều song song với cạnh của vùng đất, đồng thời ~4~ góc của khu vườn nằm ở ~4~ trung tâm của ~4~ ô đất khác nhau. Ví dụ trong hình sau, vùng đất có kích thước ~2 \times 3~ và các cách xây dựng khu vườn thỏa mãn:

Tuy nhiên, Mall có quá nhiều cách lựa chọn vị trí để xây dựng khu vườn, vì vậy muốn nhờ bạn đếm xem có tổng cộng bao nhiêu cách xây dựng khu vườn phù hợp, kết quả chia lấy dư cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên ~t~ là số lượng testcase ~(1 \le t \le 10^5)~.
• ~t~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~n~ và ~m~ ~(2 \le n,m \le 10^{18})~.

Output

• In ra số cách chọn vị trí để xây dựng khu vườn, kết quả chia lấy dư cho ~10^9 + 7~.

Examples

Sample Input

3
2 2
2 3
3 4

Sample Output

1
3
18

Scoring

• Subtask ~1~ ~-~ ~24\%~ số điểm: ~t \le 10~ ~;~ ~n,m \le 50~
• Subtask ~2~ ~-~ ~22\%~ số điểm: ~t \le 1000~ ~;~ ~n,m \le 200~
• Subtask ~3~ ~-~ ~20\%~ số điểm: ~t \le 20~ ~;~ ~n,m \le 5000~
• Subtask ~4~ ~-~ ~18\%~ số điểm: ~n,m \le 10^9~
• Subtask ~5~ ~-~ ~16\%~ số điểm: Không có ràng buộc gì thêm