Atsa is constantly looking for new ways to have fun during this quarantine, she used to play checkers against her friends but, after winning against each of them, no one wants to play checkers against her anymore. Atsa now considers to play checkers alone, but found a more interesting way to challenge herself.

A checkers board is represented by a rectangular grid with $$$N$$$ rows and $$$M$$$ columns, with a total of $$$N$$$x$$$M$$$ cells. Each cell has a light color, or a dark color, in such way that no adjacent cells have the same color, the figure below shows a checkers board with $$$8$$$ rows and $$$8$$$ columns:

Since Atsa has a lot of checkers boards, she also has a lot of stones to play checkers, she has enough stones to place at least one stone on each cell of any of her checkers boards. Similar to the cells in the board, each stone is either light colored or dark colored. Atsa found that if she places a light colored stone on each light colored cell of the board, and a dark colored stone on each dark colored cell, then all squares of $$$2$$$x$$$2$$$ cells in the board will have two dark colored stones, and two light colored stones, she defined this configuration as a "pairable" stones configurations. Atsa believes this is not the only "pairable" stones configuration in the board and decided to find all of them on each of the boards she has. Are you be able to find how many distinct "pairable" stones configurations can be placed in a checkers board?

Alan is a pastry chief owning a famous pastry shop downtown. He just received an order to prepare a lucky cake of diameter $$$10^9$$$ from a customer. If we represent a lucky cake as a circle centered in the origin, there are $$$n$$$ lucky points $$$(x,y)$$$, where each point can contain at most one chocolate chip, and a chocolate chip can only be placed in a lucky point.

Each chip can be one of $$$n$$$ different colors, and Alan has $$$n$$$ chips available of each color. A cake is called lucky if all the chips of the same color can be used as vertices of a non-degenerate triangle. In other words, for all the colors of chocolate chips used in a lucky cake, we can draw a non-degenerate triangle with all the chocolate chips of that color. The customer requires that Alan prepares a lucky cake with the maximum possible number of colors.

Help Alan to find the maximum number of colors that he can use to complete the order.

The Corporation Of Ludicrously Evil Topography and Scouring (CLETS) is working on a new way to organize their henchmen's patrols so that they will be impossible to predict for a certain handsome british spy that would try to infiltrate their base. To that end, when a henchman reaches a post, a computer will randomly pick to which post the henchman should go next.

By some classified means, we have acquired the probability distributions that the computers use to choose where to send the henchmen next. Your task is to use this information to determine, for every post, the probability that a guard will be there after $$$M$$$ steps, so that our friend, the handsome british spy, can plan the safest route to the CLETS base.

A step is defined as moving from one post to another, or waiting in the same post, should the computer decide that. The Guard start their shift on the first post.

Every seven years, in Marshaland, there is an exciting team-contest among the most daring marshmallows of the place. It consists of finding balls that were previously hidden. But the most appealing thing of this event is the reward.

The fee for enrolling in the contest is one marsh-coin, and that is the initial prize. For every ball a marshmallow team finds, the number of coins to earn doubles. So, after finding the first ball, the competitors are promised to earn 2 coins, after the second, their prize will be 4 coins, and so on. When the time is up, the judges announce exactly one winner team, that is, of course, the group with the greatest number of balls. Then, besides the coins the champion team acquired, the governor adds a bonus of $$$K$$$ coins to the prize.

The oracle of Marshaland, who never fails in her predictions, announced to the local government that she could not foresee the winner, but she had a vision: the number of members of the winner team will be the same as the number of balls they will attain to gather. Besides, this number is certainly a prime number greater than 2.

In prior years, there have been violent incidents within the first-place teams because they do not find a fair way to distribute the money. Thinking of it, the government wants to ensure that teams are shaped by exactly $$$p_1, p_2, \dots, p_j$$$ marshmallows, where the $$$p_i$$$ values are primes that meet the features stated by the oracle. That is why they have come to you; they know about your outstanding programming skills and they are asking you to find all the different $$$p_i$$$, knowing only the bonus the governor will add to the prize.

Jaime's delivery package organization is growing, the number of employees is getting bigger every month, and they bill and have earnings never seen before. Jaime decided it's time to have some hierarchy in the organization, therefore, he worked arranging the $$$N$$$ employees of his company identified with the numbers from $$$1$$$ to $$$N$$$, in such way that each employee has a manager who supervises the employee's work, the only employee who will not have a manager is Jaime. In this hierarchy, it is said that an employee $$$A$$$ reports to another employee $$$B$$$ if you can reach $$$A$$$ following the hierarchy moving through the managers starting from $$$B$$$. The reporting unit of an employee $$$A$$$ consists of all the employees $$$B$$$ such that $$$B$$$ reports to $$$A$$$, including also the employee $$$A$$$. The reporting unit of Jaime will always be the entire company (all the employees).

An organization growing is good news, and it does not mean only good news for Jaime, but for all the employees, during the last year Jaime hired a software company to develop an employee recognition program. This recognition program gives points to employees who have excelled in their work, and also it can give points to all the managerial chain of an employee if the employee has contributed significantly to the company, this is, in some cases the recognition points are earned only to an employee, in other cases the same amount of recognition points will be earned to the employee, the employee's manager, the employee's manager's manager, and so on until they reach Jaime.

Jaime has recorded all the $$$M$$$ recognition prizes the company has granted to the employees during the year, and now, he wants to answer some queries that the software he has is incapable to answer: how many recognition points employee $$$A$$$ has earned, and how many recognition points have been distributed to the entire reporting units of employee $$$B$$$. Since you have helped Jaime before, he came to you asking for help. Your task is to write a program, knowing who is the manager of each employee and the $$$M$$$ recognition prizes, to answer all of Jaime's queries.

Baker is living in a new post-modern house. A house of size $$$N$$$ consists of 5 wings arranged in a cross shape, where each wing contains $$$N$$$x$$$N$$$ rooms. For example, a house of size $$$N=$$$ 3 would be arranged as follows:

Each room is connected to the rooms adjacent to it. Baker burns one calorie walking from one room to an adjacent room. Because he is very lazy, Baker will always choose the path that burns the fewest calories. For example, when Baker goes from room $$$X$$$ to room $$$Y$$$ he will burn 5 calories.

Baker wants to know how many calories he would burn walking between every pair of rooms in a given house of size $$$N$$$. Can you help him out?

Atsa just bought Super Mario Maker and wants to test your skills for an analysis with a level that he prepared.

That level consists of a platform with some Goombas in it. As you know, Goombas are characters with the following behavior:

• Initially, they point in one direction, (left: 0, right: 1).
• They move in the direction they are currently facing, as long as there are no obstacles.
• If two Goombas collide, they will flip their direction inmediately.
• When a Goomba reaches one end of the platform, it falls.

The platform is $$$L$$$ blocks long, extending from the coordinate $$$0$$$, to $$$L$$$. Above it, there will be $$$G$$$ Goombas. The $$$i-th$$$ Goomba will be located at $$$p_i$$$ facing to the direction $$$d_i$$$. All Goombas will advance with a speed of $$$1$$$ block per second.

Atsa wants you to tell him how many seconds it will take for the platform to be empty.

For this problem purposes, consider the size of a Goomba to be a single point. No two Goombas will share the same initial $$$x$$$ coordinate.

Malva the marshmallow adopted a group of $$$N$$$ super-smart hamsters. Since Malva is super responsible, he keeps a strict quarantine and has plenty of time at home. In the middle of his boredom, Malva came up with an idea: he would train his hamster friends!

After some time of thinking, Malva decided to start the training with a game whose rules are listed below:

• Malva cuts $$$N^2$$$ cards and fills $$$N$$$ cards with the number 1, $$$N$$$ with the number 2, $$$N$$$ with the number 3, and so on.
• Malva has a whistle that plays for indicating the hamsters it is time to move on. At that moment, the hamsters take a card –whichever they want– and make a line with the $$$N$$$ cards.
• The formed line may be considered succeeded or failed. Only in the former case, Malva will reward the rodents. Because these cute animals are brilliant and really want the prize, you can be sure they will never fail.
• For a configuration to be successful, every card in the line must be greater than or equal to all the numbers to the left.
• Once finished and evaluated the line, the rodents give the cards back and prepare for the next turn.

Nlogonia casinos are very peculiar, instead of gambling, they challenge people to get the maximum "respect" points people can earn by solving some interesting mathematical problems. As the last contest of "El Gran Premio de México 2020" is running today, the casino decided to host a virtual challenge where the three contestants of a team have to work together to earn "respect" points, obviously, the more respect points the team wins, the better.

Once each of the three team members logs into the Nlogonia casino challenge platform (each using their own computer) each team member will be assigned a turn, $$$1$$$, $$$2$$$, or $$$3$$$, and each should push a button to notify they are ready to start. Once the three team members are ready the system will show a grid with $$$N$$$ rows and $$$M$$$ columns, each cell on the grid has a an integer number $$$R_{i,j}$$$, representing the amount of "respect" points the team can earn by selecting that cell, the same grid is shown to all team members. Then, the game begins. The team member with the turn $$$1$$$ has to select a rectangle from the grid, after selecting it, notifies the system and their turn is over. Next, the team member with the turn $$$2$$$ has to select another rectangle from the grid without overlapping with the rectangle selected by the team member with turn $$$1$$$, after selecting the rectangle, notifies the system and their turn is over. Last but not least, the team member with turn $$$3$$$, should select another rectangle from the grid that does not overlap with any of the rectangles selected by the other two team members, notifies the system, and then the game is over.

Once the game is over, the system will calculate the "respect" points earned by the team, this is a fairly simple calculation, the "respect" points the team will earn is the sum of the cells of the three selected rectangles. To show your skills in this challenge, you decided to write a program to find the maximum "respect" points your team can earn for a known grid from the casino system.

Polygonia (a country where everything has to be a polygon) has a scientific conflict, the progressive side, that wants to legalize circles against the conservatives, that want to keep circles illegal in order to keep their traditions.

In order to proof their advantage, the circle lovers have design a motorbyke that use circular-shaped wheels, as an attempt to replace the polygon-shaped ones, but in order to disguise the circle-ban, they have painted the wheels as if they have a regular polygon. You can see an example of them in the next image.

The motorbike has always two wheels, but in some cases, they do not represent the same polygon, for example, the front wheel is square-shaped and the back one is hexagon-shaped. In order to keep the disguise, the motorbike has to stop exactly when both wheels have one side of the polygon parallel to the ground (so it seems that it is a polygon-shaped wheel).

It is guaranteed that both wheels, despite having different polygons, are the same size. A turn is the energy needed to roll a wheel 30 degrees, it is always the same, regardless the wheel's size. It is safe to assume that when one wheel is rolled by $$$x$$$ angle, the other one, moves $$$x$$$ angle too.

So, given the wheel's circumference, the number of the simulated sides of the back and the front wheel, and a distance (in the same unit as the circumference), your task is to compute the minimum integer number of turns that are necessary to cover that distance and that guarantees that in both wheels, there is one side parallel to the ground. When the bike starts its journey, this condition is guaranteed.

As some of you may know, Jaime, the delivery package company owner, is also owner of a famous restaurant at Quadradonia. Jaime's restaurant iconic plate is an exquisite clam chowder, which is served inside a sourdough bread that is used as a bowl. The clam chowder and the sourdough bread are homemade using zero waste cooking, which means literally, to have no waste left behind while cooking a meal. What is not zero waste is the way the kitchen staff serves the bowls.

For tonights service the restaurant staff expects to serve $$$N$$$ sourdough breads of the clam chowder pouring it from the $$$M$$$ dutch ovens where the clam chowder was prepared. To make their work easier, the kitchen staff have placed the $$$N$$$ breads in a line, in such way they always know what is the next bread to be filled with soup, since all bread is homemade, not all of them may hold the same amount of soup. Also, there will be only one person serving the soup from a dutch oven at the time, so all the content that can be used from a dutch oven is used before taking the next dutch oven to use for the soup service, similar to what was done with the bread, they placed the $$$M$$$ dutch ovens in a line, so that when the person serving the soup decides to change the dutch oven, they only have to take the next dutch oven in line.

When the service starts, the first dutch oven from the line of dutch ovens is prepared for serving, and the first clam chowder should be served into the first bread from the line of breads. Before serving the soup, the staff will check, if the dutch oven has enough soup to fill the bread, then, they serve it, otherwise they will take the next dutch oven of soup from the line of dutch ovens and send the current dutch oven to the dishwasher, throwing the clam chowder left on the dutch oven as discard. Once all the $$$N$$$ breads are served, the service is over, and, as clam chowder should be fresh every night, all the soup in the current dutch oven is discarded, and the same is done to all dutch ovens from the line that were not used. As you can see, this way of serving the chowder may tend to have a lot of waste.

Jaime wants to measure how wasteful this method is, so he came to you and hired you to measure the waste. Given the volume of soup each dutch oven in the line of dutch ovens holds, and the volume of soup each sourdough bread in the line of breads needs to be filled, find how much soup will be wasted during the soup serving service.

Planet E-13 orbits around a star in a faraway galaxy named UAZ. All University students in that planet need to know well how to perform prime factorization on numbers, otherwise they risk failing the courses they take. One of the teachers likes asking the students in his class the following question: how many different prime numbers must be multiplied together (maybe some of them more than once) to obtain the same result as the product of a pair of the given numbers $$$A$$$ and $$$B$$$?

Thanitos is a student taking such course and he is really nervous; he does not want to fail. Your task is to help Thanitos answer $$$N$$$ teachers question.

Chimpa is a powerful wizard apprentice. He has been learning about magic spells lately. There are $$$m$$$ magic tuples in the world. The $$$i$$$-th magic tuple is defined as $$$(c_i, d_i, p_i)$$$, where $$$c_i$$$ and $$$d_i$$$ are lowercase letters and $$$p_i$$$ is a positive integer. A magic spell of size $$$n$$$ is a string that meets the following conditions:

• For all $$$i \in [1,n]$$$, $$$s_i$$$ is one of the first $$$20$$$ lowercase letters in the English alphabet.
• For all $$$i \in [1,n-1]$$$, there exists a magic tuple $$$(s_i, s_{i+1}, p)$$$ such that $$$i=pk+1$$$ for some non-negative integer $$$k$$$.

Recall that we denote the $$$i$$$-th character in $$$s$$$ as $$$s_i$$$.

Chimpa learned that the effect of a magic spell is unique determined by its first letter, last letter and length. There are $$$q$$$ effects that he wants to trigger. For the $$$j$$$-th effect, he wonders how many magic spells begin with the letter $$$x_j$$$, end with the letter $$$y_j$$$ and have length $$$n_j$$$. Help him to find the answer modulo $$$998244353$$$.

Jaime's package delivery company is working on a new system to reduce the spending on vehicle fuel. Basically what they will do is to reduce the amount of fuel they load on a vehicle before it starts with its delivery order. Each morning Jaime takes a vehicle from warehouse $$$1$$$ which can hold a maximum of $$$F$$$ fuel to deliver $$$K$$$ packages, each of these packages should be delivered on one of the $$$N$$$ warehouse of Jaime's company, no two packages will be delivered in the same warehouse, and some warehouses may not receive a package in a day, also, Jaime can deliver the packages in any order he decides. Some warehouses have a fuel pump that can be used to load a maximum of $$$f_i$$$ fuel into the vehicle, Jaime can go to a warehouse even if he does not have to deliver a package to it just to load fuel, and everytime he goes to the a warehouse with a pump, he can load fuel even if he already loaded fuel in that warehouse.

As part of their vehicle fuel reduction program, Jaime has measured the amount of fuel $$$c_{u,v}$$$ it takes to travel from one warehouse to another. As measuring all pairs of warehouses is difficult and costly, Jaime measured only $$$M$$$ pairs of them. Jaime will make sure to travel from one warehouse $$$u$$$ to another warehouse $$$v$$$ during his delivery task only if he knows beforehand the amount $$$c_{u,v}$$$ of fuel he needs, and if the vehicle has at least $$$c_{u,v}$$$.

Jaime needs your help to determine what is the minimum amount of fuel he has to load on the vehicle before he starts his delivery task in order to deliver the $$$K$$$ packages and return to warehouse $$$1$$$?