After years of investigation and pursuit, the fugitive Miguelez, accused of high treason against USP (Union of Solar Planets), was captured by the famous space detective Morete. Due to the gravity of his crime, he was sent to the maximum-security prison on Neptune, which employs the panoptic system: all 360 cells of the complex are arranged along a circle, numbered from 1 to 360, with the watchtower located at the center of this circle, allowing the prison guard to see all the cells.

Detective Morete is concerned that Miguelez may plot an escape, so he wants to enhance surveillance of the prison cells by installing a new set of cameras in the watchtower, which will cover a single contiguous interval of cells. Morete has access to the record of which cells are occupied in the complex and wants to install the cameras in such a way that they cover the entire set of these cells; however, due to budget constraints, he wants to determine the size of the smallest interval of cells that need to be monitored to ensure all occupied cells are observed.

Busy with his duty to uphold the law, Morete has requested your assistance: given the $$$n$$$ cells $$$c_i$$$ in the circle that are occupied, what is the minimum number of cells that should be covered by the cameras so that all occupied cells are under surveillance?

Nathan is a shrewd interplanetary gambler who spends his life deceiving extraterrestrials. On one of his expeditions to Uranus, our space duelist challenged an alien by saying he could beat him in any game of his choosing, imagining that his tricks would guarantee victory. Then, the alien proposed an intense intellectual battle.

Upon learning the rules of the battle, Nathan finds himself in a predicament and ends up asking for your help. Pay close attention, because the rule is somewhat complex: in the first round, the Uranian will say an integer $$$n$$$. In the second and final round, it will be Nathan's turn to say an integer $$$m$$$. The winner is the one who says the larger number.

After knowing the number $$$n$$$ said by the alien, your task is to determine which number $$$m$$$ will guarantee victory for Nathan.

With the approaching Interplanetary Programming Marathon, Enrique, the Coach of the Union of Solar Planets Marathon Group (MaratonUSP), is determined to bring all $$$n$$$ members of the group to participate in this historic competition, which will be held on Earth for the first time.

Members of MaratonUSP are organized into teams of $$$3$$$ members. Enrique is confident that the members will be excited about the opportunity to compete with talents from across the universe. He understands that, to ensure the participation of each team, he only needs to convince the majority of the 3 members, as the last member will immediately agree to participate.

With a tight schedule, the Coach seeks your assistance in determining the minimum number of people he needs to convince to participate in the Interplanetary Programming Marathon, ensuring that all MaratonUSP teams agree to compete in this space event.

Carlinhos, the best pizza maker in the solar system, discovered a new technique for cooking his pizzas: baking them on the Sun! The news of Carlinhos' new pizzas quickly spread throughout the galaxy. So, Rachel and Matheuzin, space pizza sommeliers, decided to travel to the Sun to try the novelty.

Rachel and Matheuzin went to Carlinhos' pizzeria with a group of $$$2n$$$ friends, each of whom has a favorite pizza flavor. Since they spent a lot of money on the trip, they decided to save on pizzas. Therefore, they will order $$$n$$$ pizzas, each divided into two halves of different flavors. The price of a pizza whose halves have values $$$p$$$ and $$$q$$$ is $$$\max(p,q)$$$.

Help Rachel and Matheuzin find a way to pay as little as possible for the pizzas.

It is finally time for humanity to colonize Mercury. However, a major problem for creating cities on the closest planet to the Sun is its rugged terrain. For proper city construction, the terrain of the planet needs to be leveled.

Paulo is a flat-earther (i.e., someone who flattens the earth) from IME (International Mercury Excavation), hired to fix Mercury's terrain. Mercury's horizon consists of $$$n$$$ hills, each with a height $$$a_i$$$. Due to the quantum nature of Mercury's sand, it is not possible to move sand between hills, so Paulo can only reduce their height and never increase it.

Antônio, president of the ACM (Association for the Conservation of Mercury), is very concerned about the changes that will be made to the planet and would like the terrain to be altered as little as possible, that is, the total number of meters of sand removed should be minimized. Paulo, being a natural flat-earther, is not good at math and needs your help to calm Antônio. Help Paulo determine the minimum meters of sand that must be removed from Mercury's hills so that the terrain is uniform.

The Festival of the Moon is an anual tradition from the people of the Moon. Every waning moon, beings from all around the solar system gather to celebrate and dance around flaming craters. It is also a great oportunity to experience the great lunar cuisine, like the cheese bread made from the soil cheese in the moon.

This lunar year, May is responsible for the organization of such an important festival. With all her influence and popularity, she invited lots of planets to gather on this special date. However, May was worried that the own lunar people wouldn't appear at the meeting, since they show less and less interest over the years to participate in their own tradition, prefering to gather on the dark side and party on their own way.

Cauê, who was responsible for managing and selling the tickets, suggested an ideia: the organization could use the money they won from USP (Union of Solar Planets) through PIPA prize (Program of Incentive for Playful Activities, which aims to invest in the best parties in the Solar System), to offer tickets for half the price to the Festival of the Moon, exclusively to lunar people.

The tickets were sold and the party rocked hard. Cauê was having so much fun that he made a terrible accounting mistake: he forgot to count how many people in the party were from the Moon, and wouldn't be able to establish a good metric to check whether or not his idea was good.

Cauê then asks your help to solve this problem before he gets fired. Luckily, he was still able to write down the ammount raised, $$$a$$$, in lunar currency, and how many people, $$$p$$$, went to the festival. You may assume that everyone who bought a ticket went to the party. With this information, and with the full price of the ticket, $$$v$$$, help Cauê find out how many people at the party were from the Moon.

The planet Venus is known for its toxic atmosphere and infernal temperatures, where apparently any civilization would be unable to live and thrive. However, records of an ancient civilization (the "Venirics") that inhabited Venus millions of years ago have been recently detected on this planet.

Faced with this surprising discovery, the Union of Solar Planets (USP) decided to send to this planet the only specialist capable of retrieving these records and revealing more details about the history of the Venutian civilization: the space archaeologist Otávio.

In his extensive research, Otávio discovered surprising facts about the generations of Venirics:

• Generation $$$0$$$ of the Venirics was composed of exactly $$$a \geq 1$$$ inhabitants.
• In the life cycle of a Veniric capable of reproduction, they have exactly $$$r \gt 1$$$ offspring through asexual reproduction. The value of $$$r$$$ is the same for Venirics of any generation. That is, if all $$$a$$$ Venirics from generation $$$0$$$ were capable of reproduction, then generation $$$1$$$ was composed of exactly $$$ar$$$ Venirics, and so on.
• Due to a genetic reason still unexplained, all individuals of a certain generation $$$m \geq 0$$$ were unable to reproduce, but all individuals up to the previous generation were capable of reproduction. Thus, the Venirics civilization ended after the death of individuals from generation $$$m$$$.

The only intact record that Otávio found about the size of the historical Venirics population was its total number (i.e., the sum of the sizes of all populations from generation $$$0$$$ to generation $$$m$$$), but he was unable to deduce anything about the values of $$$a$$$, $$$r$$$, and $$$m$$$, and therefore asked for help from Marcelo, the space computer scientist.

Marcelo was also unable to deduce the values of $$$a$$$, $$$r$$$, and $$$m$$$ from $$$n$$$, as he wisely noticed that different values of these parameters could have led to the same value of $$$n$$$. The only thing he knows is that there are not many possibilities for the sizes of the generations given $$$n$$$, and he wishes to determine how many there are.

Since returning from the toxicity of Venus, however, he can no longer type, and so he asked you to write a program that answers the question for him.

As part of the celebrations for the 90th anniversary of its creation, the Union of the Solar Planets (USP) decided to pay tribute to Saturn. The tribute will also serve as a symbol of the peace treaty to be signed between the USP and the kingdom of Saturn, ruled by the malevolent monarch Mori.

When consulted about the tribute, the malevolent monarch Mori ordered the construction of a gigantic necklace of asteroids for his planet. After all, what good are rings without a necklace? Furthermore, as if the task were not already fantastical enough, to symbolize the ideals of freedom and equality of the treaty, each asteroid must be either amber (a) or blue (b), coincidentally the colors of the USP flag.

To carry out this astronomically proportioned challenge, two space jewelers with vast experience in colorful asteroids, Rafael and Pedro, were summoned. The task proved even more difficult than the jewelers expected, but with little time remaining before the deadline, they managed to complete the construction of a string with $$$n$$$ amber and blue asteroids, without a specific order.

Only the final step of joining the two ends of the string remained when the monarch Mori maliciously machinated yet another restriction on the tribute: now, one half of the necklace must consist only of amber asteroids and the other half only of blue asteroids. Considering the tight deadline and the colossal proportions of the project, the jewelers would not be able to construct a new string in time. Then an idea emerged: remove a contiguous segment of the string (possibly the entire string) and join the two ends of this segment to form a necklace that meets the new restrictions.

Now Rafael and Pedro need to assess the feasibility of this plan and have asked for your help to determine the maximum size (in number of asteroids) of a necklace that can be created with this technique, also meeting the restrictions that the malevolent monarch Mori maliciously machinated. Note that a necklace of size zero is also valid according to the restrictions, and that the initial string is not circular, meaning the first and last asteroids are not initially connected to each other.

Nathalia, a software engineer and marathon enthusiast, is currently engaged with the MaratoNasa development team, working on the Mars exploration project. Her role is crucial in developing the software for the incredible exploratory robot K-IA-FFA.

The planet Mars is represented by a board with dimensions $$$n$$$ by $$$m$$$, where '$$$\#$$$' indicates a wall and '$$$.$$$' represents an empty space. Nathalia is currently in the testing stage of the final version of the K-IA-FFA software, which commands the movements of the exploratory robot. Her task is to evaluate the software's effectiveness in terms of board coverage.

The operation of the software follows a logical pattern:

• If possible, the robot moves forward one square in the current direction.
• Otherwise, it rotates $$$90^\circ$$$ counterclockwise and tries to move forward again.

It is important to note that the edges of the board are also considered walls to prevent the robot from escaping. Nathalia needs to calculate how many distinct squares on the board the robot will be able to visit in various possible scenarios.

In 2024, the Union of the Solar Planets (USP) is celebrating its 90th anniversary! To mark this occasion, Maystronauta and Astronauthan organized a dinner for the members of MaratonUSP at the best restaurant in the solar system, Red Spot, on Jupiter!

Upon arriving at the restaurant, the $$$n$$$ members of MaratonUSP sat at a single table with chairs numbered from $$$1$$$ to $$$n$$$. The person in position $$$i$$$ ordered dish number $$$a_i$$$. The renowned chefs Willian Fogaça Mori and Nathália Carosella Tsuno will take care of cooking the dishes for the evening, but the space waiter Thilio will need your help.

Like any other common Jovian, Thilio has $$$k$$$ arms. He can carry as many dishes as needed with each of his arms but with one restriction: all the dishes must be identical. For example, if everyone ordered dish 1, Thilio would be able to serve the entire table with just one arm. However, if someone ordered dish 1 and someone else ordered dish 2, he would need to carry one dish in each arm. According to the restaurant's rules, the waiter must serve a continuous range of people, i.e., choose values $$$\ell$$$ and $$$r$$$ and serve all the customers seated in the interval $$$[\ell, \dots, r]$$$.

As Thilio is a big fan of competitive programming, he would like to serve the maximum number of MaratonUSP members possible. He needs your help to find an interval $$$[\ell, \dots, r]$$$ of maximum length such that all the orders within this interval can be carried with his $$$k$$$ arms.