Ba bé Naot, lastPledge và LeThanhMinh cùng tham gia một trò chơi mang tên "Ba chàng lính ngự lâm". Trò chơi được diễn ra trên bảng ~N\times M~, ba bé sẽ chọn ba ô khác nhau trên bảng sao cho không có người nào có thể đi đến vị trí của người khác bằng một bước di chuyển theo hướng của quân mã trong cờ vua. Hãy đếm số trạng thái khác nhau của trò chơi (hai trạng thái được gọi là khác nhau nếu có ít nhất một người đứng ở hai vị trí khác nhau trong hai trạng thái đó).

Input

Dòng đầu tiên chứa một số nguyên dương ~T~ là số bộ test (~T\le 10000~).

~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~N~ và ~M~ (~1 \le N, M \le 10^{9}~) ứng với một bộ test.

Output

Với mỗi truy vấn in ra số trạng thái khác nhau chia lấy dư cho ~10 ^ {9} + 7~.

Subtask

• ~20\%~ số test có ~T\le 10, 1\le N * M \le 1000~.

• ~80\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

2
2 3
5 4

Sample Output 1

72
3732