Cho số nguyên dương ~ n ~ và dãy số ~ a_1, a_2,…,a_n ~ trong đó ~ a_i = i ~. Hãy cho biết có bao nhiêu cặp số ~ (a_i, a_j) ~ mà ~ a_i + a_j ~ chia hết cho ~ k ~ và ~ i < j ~.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ t ~ ~ (t ≤ 100) ~ cho biết số lượng testcase
• ~ t ~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương lần lượt là ~ n ~ và ~ k ~ ~ (1 ≤ k ≤ 10000; k<=n<=10^9 )~;

Kết quả

• Mỗi testcase in kết quả trên một dòng

Ví dụ:

Input 1

2
10 4
7 3 

Output 1

10
7