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

Fahim Shahriar Shakkhor