Minimum Hospitals Required

In a rural region, there are N villages arranged in a straight line. The local government wishes to ensure that every village has access to a hospital. A hospital built in any village can serve that village as well as its immediate neighbors (i.e. the village immediately to its left and right). Therefore, one hospital can cover at most three consecutive villages.

Your task is to determine the minimum number of hospitals needed so that every village is covered. The answer can be mathematically represented using the ceiling function as follows:

$$ \lceil N/3 \rceil $$

Note that although additional information (an array of integers representing village populations or identifiers) is provided for each test case, the coverage decision depends solely on N, the number of villages.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer T, representing the number of test cases.
• For each test case, there are two lines:
  • The first line contains a single integer N, the number of villages.
  • The second line contains N space-separated integers. These integers represent village populations or identifiers (they do not affect the computation).

outputFormat

For each test case, output a single line with one integer — the minimum number of hospitals required.

1
2
100 200

1