该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师建造了一座楼塔，第i层有i*i个房间，每个房间可以容纳m人，他想知道问n层的楼塔可以容纳多少人

Format

Input

第一行一个正整数$T(1 \leq T \leq 10^3)$，表示测试组数

对于每组测试，给定两个正整数$n, m(1 \leq n, m \leq 3 \times 10^3)$，表示楼层和每个房间可以容纳的人数

Output

输出一个整数表示可以容纳的人数

Samples

1
1
1

1

Limitation

1s, 1024KiB for each test case.