Long time ago there studied a boy named Golu in NIT Jamshedpur. He fell in love with a girl named Golaayi in the institute. After a lot of encouragement and love tips from his friends he finally decided to propose the Golaayi. Golaayi being pattern frenzy gave him two integers N and K and a pattern given below

          K K
     2*K 2*K 2*K
  3*K 3*K 3*K 3*K
4*K 4*K 4*K 4*K 4*K
.
.
.
N*K N*K N*K . . . N+1 times

Here the i_th row has i*K i+1 times.

Golaayi will only accept Golu's proposal if he finds the total sum of the pattern till N lines. Golu comes to you for help as you are the love guru and the best mathematician of the batch.

Input

The first line on the input contains the a single integer T denoting the number of test cases. The first and only line of each test case contains a two space separated integers N and K.

Output

For each test case, print a single line containing a single integer denoting the total sum of the pattern.

Constraints

1 ≤  T ≤ 10⁵
1 ≤  N  ≤ 10⁴
1 ≤  K  ≤ 10³