Before the invention of electrical wireless communcations (such as the telegraph), relaying information over a long distance could take a great deal of time. One could write a letter and have it delivered by hand, but while such a message could carry detailed informaiton, it could only travel as fast as the man carrying it.
Another option is the use of long-range visual beacons, which can relay low-detail messages at higher speeds. The Ancient Greeks used Phryktories - large towers on mountaintops on which a fire could be lit. If a single tower lit its beacon, all other towers within visible range (about 20 miles) would quickly light their fire beacons as well. So then if any city was attacked they would light the nearby fire beacon, and soon all other cities neighboring cities would see the chain of fire beacons and be alerted to the attack.
You are in charge of designing a valid fire beacon network to cover a large area connecting many distant cities.
Each city has neighboring cities, and a fire beacon tower lit in any given city will be visible from another fire beacon tower in a city up to three neighbors away.
(To clarify, if cities are lined up a b c d, then towers in cities a and d could see each other even if no towers existed in cities b nor c)
In the event of an attack, a city could either light a fire beacon on a tower built within their own city, or if they have no tower they could alert a neighboring city to light their beacon instead.
In order for a fire beacon network to be valid, the following conditions must be true: A) each city has a tower or has a neighbor with a tower, and B) all towers are part of the same visible network, such that lighting one tower would cause all of them to be lit.
The easiest solution would be to build a fire beacon tower in each city, but this is inefficient - far fewer towers are required. You will be required to calculate the minimum quantity of towers required to be built.
There are many cities, so you will be expected to procedurally generate the map of neighboring cities yourself, using the Linear Congruential Generator (use a = 445, c = 700001, m = 2097069).
To generate a map of n cities, first use some given seed x0 to generate an array of n-1 random numbers in a 1-indexed list names edges.
Then for each number edges[i] = r, we will say that the city numbered i is neighbors with the city numbered r mod i.
For example, let's generate a map of 10 cities using x0 = 9001.
i │ r │ r mod i
───┼─────────┼─────────
1 │ 511308 │ 0
2 │ 1748609 │ 1
3 │ 818407 │ 1
4 │ 1110 │ 2
5 │ 1193951 │ 1
6 │ 1449739 │ 1
7 │ 2033673 │ 5
8 │ 1847747 │ 3
9 │ 896368 │ 4
This tells us:
City 1 is neighbors with city 0.
City 2 is neighbors with city 1.
City 3 is neighbors with city 1.
City 4 is neighbors with city 2.
City 5 is neighbors with city 1.
City 6 is neighbors with city 1.
City 7 is neighbors with city 5.
City 8 is neighbors with city 3.
City 9 is neighbors with city 4.
By building towers at cities 1, 3, 4, and 5 then every city will have a tower either within the city or in a neighboring city, and every tower is at most two neighbors away from another tower. It can be proven that the minimum quantity of towers required to achieve these goals is 4.
Input Data
Firts line will be Q, the quantity of testcases.
Q lines will then follow, each with two integers n x0, being the number of cities and the seed of the Linear Congruential Generator, respectively.
Answer
Should consist of Q space-separated values, being the minimum required towers necessary to form a valid fire beacon network.
Example
input data:
2
10 9001
3456 65504
answer:
4 1234