Prime Time Again Problem Statement

You are given two integers DAY_HOURS and PARTS. Consider a day with DAY_HOURS hours, which can be divided into PARTS equal parts. Your task is to determine the total instances of equivalent prime groups, where a prime group is defined as a set of hour values that are prime and occur at the same position in different parts of the day.

Example:

Input:

DAY_HOURS = 20
PARTS = 2

Output:

2

Explanation:

If we divide the day into 2 parts, we have:

Part 1: 1  2  3  4  5  6  7  8  9 10
Part 2: 11 12 13 14 15 16 17 18 19 20

• 3-13 is a prime group, as both numbers are prime.
• 7-17 is a prime group, as both numbers are prime.

There are 2 prime groups in total.

Constraints:

• 1 <= T <= 100
• 10 <= DAY_HOURS <= 5 * 10^3
• 2 <= PARTS <= 10^3
• Time Limit: 1 second

Input:

The first line of input contains an integer T representing the number of test cases.
The first and only line of each test case contains two space-separated integers DAY_HOURS and PARTS.

Output:

Output a single integer for each test case, representing the number of equivalent prime groups.

Note:

• The day starts with hour 1 and ends with hour DAY_HOURS.
• Each hour in a prime group must be in a different part of the day.
• If there is no prime group, return zero.
• DAY_HOURS should be divisible by PARTS.