Covering an equilateral triangle

Time limit1sMemory limit256 MB

Summary

Cover an equilateral triangle of side A with the smallest possible number of side-B equilateral triangles, which is (A/B) squared.

Level: Easy1 of 10
Topics: Math
Solved: No attempts yet

Problem

You want to cover an equilateral triangle with side length $A$ completely by equilateral triangles with side length $B$ . You may use as many small triangles as you like, and you may flip a small triangle upside down.

The two integers $A$ and $B$ satisfy $B \le A$ , and $A$ is divisible by $B$ . Find the minimum number of small triangles needed to cover the large one.

Input

The first line contains the number of test cases $T$ ( $T \le 100$ ).

Each of the next $T$ lines contains one test case: two integers $A$ and $B$ ( $1 \le B \le A \le 1\,000$ , $B$ divides $A$ ).

Output

For each test case, print on its own line the minimum number of equilateral triangles with side length $B$ that cover an equilateral triangle with side length $A$ completely.

Examples4

Example 1
Input
```
2
2 1
3 3
```
Expected output
```
4
1
```
Example 2
Input
```
1
1 1
```
Expected output
```
1
```
Example 3
Input
```
1
1000 1
```
Expected output
```
1000000
```
Example 4
Input
```
1
1000 1000
```
Expected output
```
1
```