# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Utkarsh Gupta

*Jeevan Jyot Singh*

**Preparer:***Tejas Pandey*

**Tester:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

800

# PREREQUISITES:

None

# PROBLEM:

How many K\times K squares can you cut out of an N\times N grid?

# EXPLANATION:

The answer is simply

where \left\lfloor \cdot \right\rfloor denotes the floor function. This is `N/K`

in C++/Java and `N//K`

in Python.

## Proof

Any given row or column can only hold \left\lfloor \frac{N}{K} \right\rfloor squares, since any more than that would require more than N squares in that row/column.

So, \left\lfloor \frac{N}{K} \right\rfloor \times \left\lfloor \frac{N}{K} \right\rfloor is clearly an upper bound for the answer.

This upper bound is easily seen to be achievable by greedily picking K\times K squares from the top left corner, so it is also the answer.

# TIME COMPLEXITY

\mathcal{O}(1) per test case.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, k = map(int, input().split())
print((n//k) * (n//k))
```