# DCP-520: Prime Size Squares Inside Rectangle Back to All Problems

Hard Math > Counting

You have a rectangular grid of size **n x m**. Find the total number of different possible squares in it whose sides are aligned to the sides of the rectangular grid and the length of the side of the square is a [Prime][2]. Input: ------ Input starts with an integer **T (1<=100,000)**, denoting the number of test cases. Each case contains two integers **n (1 ≤ n ≤ 1,000,000)** and **m (1 ≤ m ≤ 1,000,000)**. Output: ------- Print the answer for each testcase in a single line. Sample Input ------------ 5 1 1 2 2 2 3 3 3 3 4 Sample Output ------------- 0 1 2 5 8 **Explaination:** In a **3 x 3** grid , there are (**4** squares of length **2**) and (**1** square of length **3**). Total = **5**. ![enter image description here][1] [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/049d8f5c-9f09-cac9-ef55-08d5971b2eed_cdc5897c2d2e4229b92d85131dece478_W702xH447.png [2]: https://en.wikipedia.org/wiki/Prime_number

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 30/104

Solve/Submission

### Ranking

# User Language Timing
01 feodorv C 0.05s
03 ssavi Cpp 0.07s
04 dot0 Cpp 0.07s
05 kisu_pari_na Cpp14 0.07s
06 seyedssz Cpp 0.08s
07 ovis96 Cpp14 0.08s
08 Hasinur_ Cpp 0.09s
09 tariqiitju Cpp 0.10s
10 Zeronfinity Cpp 0.10s
11 nasif2587 Cpp 0.10s
12 PKP_007 Cpp 0.10s
14 mhiceiu Cpp 0.11s
15 prateepm Cpp14 0.15s
17 Nirjhor Cpp 0.19s
18 shamimjucse Cpp 0.20s
19 Nobel Cpp 0.20s
20 mh755628 Cpp 0.23s
21 dipta007 Cpp 0.23s
22 Bruteforcekid Cpp 0.26s
23 Jakir_Hossain_Sust Cpp 0.27s
24 Towfiq379 Cpp 0.30s
Feedback