Cho 2 số nguyên dương ~n~ và ~m~.

Yêu cầu: Đếm số cặp số nguyên dương ~a, b~ sao cho ~a < b \le n~ và ~a + b~ chia hết cho ~m~.

Input

• Dòng đầu là số nguyên dương ~T~ là số test (~T \le 10^5~).
• ~T~ dòng tiếp theo thể hiện ~T~ test, mỗi dòng gồm 2 số nguyên dương ~n~ và ~m~ (~n, m \le 10^9~).

Output

• Ghi ra ~T~ dòng, mỗi dòng là kết quả một test.

Sample Input 1

3
2 3
4 3
1 6

Sample Output 1

1
2
0