Saki is cleaning up the data obtained from false minoshiro she has captured. The data consists of all non-negative integer sequences of length equal to $$$N$$$, where each integer is less than $$$M$$$.

For a sequence $$$s$$$ in the data, we write $$$s=[s_0, \cdots, s_{N-1}]$$$ where $$$s_i$$$ is the $$$i$$$-th integer in $$$s$$$.

Let $$$\pi(s)$$$ be the length of the longest proper prefix that is also a proper suffix. i.e. it is the maximum non-negative integer $$$p$$$ with $$$p \lt N$$$ such that $$$s_i = s_{N-(p-i)}$$$ for all integer $$$0 \le i \lt p$$$. Note that the maximum always exist as $$$p=0$$$ satisfies the condition. When Saki cleans up sequence $$$s$$$, she saves $$$\pi(s)^2$$$ amount of effort.

Saki now wants to know the sum of all efforts she will save when she cleans up the entire data. Write a program to find the sum, modulo $$$998\,244\,353$$$.

Saki would like to install sewage system in two villages $$$A$$$ and $$$B$$$, each containing $$$N$$$ houses numbered from $$$0$$$ to $$$N-1$$$. For each village, the house numbered $$$0$$$ is located at the highest altitude, while the house numbered $$$N-1$$$ is located at the lowest altitude.

Saki will order $$$2$$$ pipes for each of the $$$M$$$ types of pipes, for the total of $$$2M$$$ pipes. Saki will install $$$M$$$ pipes of different types to each village.

Each pipe has a fixed non-negative integer capacity, and connects two different houses of the same village. Two pipes of the same type have the same capacity. Note that some pipe may have zero capacity (such pipes are for cosmetic purposes). It is already determined which pipe connects which houses, but the capacities have not yet been determined.

After installation, the maximum flow of water in each village is defined as the maximum flow from $$$0$$$ to $$$N-1$$$ when the given sewage system is interpreted as an undirected flow network.

As the village $$$B$$$ has a bigger population than $$$A$$$, Saki would like the maximum flow of water of village $$$B$$$ to be strictly greater than that of $$$A$$$. She can ask pipemakers to set the capacity of each type of pipe to any non-negative integer she wants, but she hasn't decided on the values.

Write a program to help Saki determine if it is possible to assign non-negative integer capacity to each pipe so that the maximum flow of water of village $$$B$$$ is strictly greater than that of $$$A$$$, and if possible, show one possible way to assign capacities.

The unified class is hosting a cantus tournament where classes A and B advanced to the final. However, during the final match, there was an accident where the cantus of the students are entangled together. Saki is tasked with dealing with this situation as soon as possible.

The students are located in an infinite grid, where the rows and columns are numbered with integers. The cell at the $$$i$$$-th row and $$$j$$$-th column is represented as $$$(i, j)$$$, and it is known that all the students occupy a distinct cell, and their location satisfy $$$0 \le i \lt N$$$ and $$$0 \le j \lt M$$$.

Saki will attempt to separate class A and B students from each other, if possible. In one move, she can pick either class A or B, and order every student in that class to simultaneously move one cell in one of four directions: right, up, left, or down. She cannot perform the move if it would result in a student from class A and a student from class B being in the same cell.

Write a program to help Saki determine if it is possible to separate class A and B. They are considered separated if the smallest euclidean distance between a student from class A and a student from class B is at least $$$10^{9999999999999999999999}$$$.

As the head of the Ethics community, Saki is charged with overseeing the railway construction over $$$N+1$$$ sites, numbered from $$$0$$$ to $$$N$$$. It is known that for some unknown positive integer $$$x$$$, geotechnical engineers figured out the following list of candidate bidirectional paths that railways can be constructed upon.

• For each integer $$$1 \le i \lt N$$$, there is one candidate between the $$$i$$$-th and $$$i+1$$$-th site.
• There are $$$x-1$$$ candidates between $$$0$$$-th and $$$1$$$-st site.
• For each integer $$$2 \le i \lt N$$$, there are $$$2x-2$$$ candidates between $$$0$$$-th and $$$i$$$-th site.
• There are $$$2x-1$$$ candidates between $$$0$$$-th and $$$N$$$-th site.

Saki is planning to pick $$$N$$$ of the candidates and build railways so that all $$$N+1$$$ sites are connected either directly or indirectly. She has countably-infinite many friends, numbered $$$1, 2, 3, \cdots$$$. She asked the friend numbered $$$1$$$ to compute the number of ways to pick such a set of candidates whenever Saki choose the value $$$x$$$. Let the correct answer be $$$f(x)$$$.

To make sure, each friend $$$i$$$ asked the friend $$$i+1$$$ to double-check the computation. However, due to a mistake in their communication, when friend $$$i$$$ received the integer $$$y$$$, he/she passed the value $$$f(y)$$$ to friend $$$i+1$$$ instead of the value $$$y$$$. Therefore, friend 1 computed $$$f(x)$$$, friend 2 computed $$$f(f(x))$$$, the friend 3 computed $$$f(f(f(x)))$$$, and so on.

However, one of Saki's friend Satoru noticed that regardless of the value $$$x$$$ Saki chose, for some fixed prime $$$M$$$, his computation result was always equal to $$$x$$$ modulo $$$M$$$. Satoru now wonders what his friend number would be, which is a positive integer, unless there were some mistakes in one of the computations.

Given $$$N$$$ and $$$M$$$, write a program which determines whether this was possible, and if possible, find the minimum friend number of Satoru, modulo $$$998\,244\,353$$$.

This is an output-only problem.

In order to avoid repeating the tragedy that unfolded in her childhood, Saki invented a device which drastically lowers the probability of the Karma Demon appearing!

The earth can be modeled as a sphere with radius $$$1$$$, and Saki is planning to install $$$100\,000$$$ devices on its surface. The effectiveness of the devices is known to be proportional to the number of pairs of devices with Euclidean distance exactly $$$\sqrt2$$$. Here, the Euclidean distance between two people with coordinate $$$(x_0, y_0, z_0)$$$ and $$$(x_1, y_1, z_1)$$$ is $$$\sqrt{(x_0 - x_1)^2 + (y_0 - y_1)^2 + (z_0 - z_1)^2}$$$.

Write a program to install $$$100\,000$$$ devices on distinct locations, such that there exists at least $$$1\,400\,000$$$ pairs of devices with Euclidean distance exactly $$$\sqrt2$$$.

$$$N$$$ people, numbered from $$$0$$$ to $$$N-1$$$, are taking part in the summer festival in Kamisu 66. Kamisu 66 can be represented as a coordinate plane, where $$$i$$$-th person is located at $$$(X_i, Y_i)$$$.

A set of people is said to be in a ritual formation if there exists exactly one circle for which every person in the set lies on its circumference.

Saki would like to know how many sets of people are in a ritual formation. Write a program to help Saki compute the answer, modulo $$$998\,244\,353$$$.

A cantus user's status is characterized by a complex number where both real and imaginary parts are integers. Let $$$\mathbb{G}$$$ be the set of all such complex numbers.

Let's say $$$x \in \mathbb{G}$$$ divides $$$y \in \mathbb{G}$$$ if there exists $$$k \in \mathbb{G}$$$ with $$$k\cdot x = y$$$.

$$$x, y \in \mathbb{G}$$$ are said to be uncorrelated if $$$1$$$, $$$-1$$$, $$$i$$$, $$$-i$$$ are the only element of $$$\mathbb{G}$$$ dividing both $$$x$$$ and $$$y$$$. Otherwise, $$$x$$$ and $$$y$$$ are said to be correlated.

Saki knows that the probability of a cantus user turning into a karma demon is proportional to a quantity called the isolation index. For a cantus user with status $$$x \ne 0$$$, the isolation index is computed as follows.

1. Partition $$$\mathbb{G}$$$ by the following equivalence relation: $$$y \sim z$$$ iff $$$x$$$ divides $$$y-z$$$. It can be proved that there are only finite number of equivalence classes.
2. For each equivalence class $$$C$$$, it can be proved that either every element in $$$C$$$ is correlated with $$$x$$$, or every element in $$$C$$$ is uncorrelated with $$$x$$$.
3. The isolation index is the number of the equivalence classes $$$C$$$ such that every element in $$$C$$$ is uncorrelated with $$$x$$$.

Saki wants to compute the sum of the isolation index of all non-zero status $$$a+bi \in \mathbb{G}$$$, $$$a \in \mathbb{Z}$$$, $$$b \in \mathbb{Z}$$$ with $$$a^2+b^2 \le N$$$. Write a program to help Saki find the desired sum.

This is an output-only problem.

Saki has invented a new programming language called Tree++. A program in Tree++ can be represented as a rooted binary tree where each non-leaf node has exactly two children, and has one of the following labels: "add", "sub", "mul", "quo", "rem", "pow". Here, a leaf node of a rooted tree is a node with no child.

A program in Tree++ accepts an integer $$$X$$$, and either outputs an integer, or produces an error according to the following rule.

1. The program first writes the integer $$$X$$$ on each of the leaves.
2. For each non-leaf node $$$u$$$ in decreasing order of depth, let $$$L$$$ and $$$R$$$ be the integer written on the left and right child.
   • If the label of $$$u$$$ is "add", $$$L+R$$$ is written on $$$u$$$.
   • If the label of $$$u$$$ is "sub", $$$L-R$$$ is written on $$$u$$$.
   • If the label of $$$u$$$ is "mul", $$$L\cdot R$$$ is written on $$$u$$$.
   • If the label of $$$u$$$ is "quo", it produces an error if $$$R \le 0$$$. Otherwise, the largest integer $$$q$$$ with $$$q\cdot R \le L$$$ is written on $$$u$$$.
   • If the label of $$$u$$$ is "rem", it produces an error if $$$R \le 0$$$. Otherwise, the unique integer $$$0 \le r \lt R$$$ which makes $$$L-r$$$ an integer multiple of $$$R$$$ is written on $$$u$$$.
   • If the label of $$$u$$$ is "pow", it produces an error if $$$R \lt 0$$$. Otherwise, $$$L^R$$$ is written on $$$u$$$. In particular, if $$$R=0$$$, $$$1$$$ is written on $$$u$$$ regardless of the value of $$$L$$$.
3. If at any moment an integer with absolute value greater than $$$2^{100\,000}$$$ is written on a node, it produces an error.
4. If an integer is successfully written on all nodes without an error, the program outputs the integer written on the root.

Satoru does not believe in the power of Tree++, so he challenged Saki to implement a short membership test for the 5 of his favourite numbers: $$$561$$$, $$$1105$$$, $$$1729$$$, $$$2465$$$, and $$$2821$$$. (Note that these are the 5 smallest Carmichael numbers, i.e. the composite numbers $$$x$$$ with $$$a^x=a \mod x$$$ for all integer $$$a$$$) More specifically,

1. Saki must implement a program in Tree++ with the number of nodes equal or less than $$$150$$$.
2. Satoru will run the program for the inputs $$$x=100, 101, \cdots, 3000$$$.
3. For each $$$x$$$, the program must output $$$1$$$ if $$$x \in \lbrace 561, 1105, 1729, 2465, 2821\rbrace$$$, otherwise it must output $$$0$$$, without an error.

Write a program to help Saki implement the membership test.

Saki is interested in various ways to encode a tree into a sequence ever since she has invented Tree++, especially the Prüfer sequence.

Given a tree with $$$N$$$ nodes labelled from $$$0$$$ to $$$N-1$$$, the Prüfer sequence of the tree is the sequence obtained by the following process.

1. Initialize the sequence to be empty.
2. Repeat the following $$$N-2$$$ times: pick the leaf with the smallest label, append to the sequence the only neighbor of the leaf, and then erase the leaf along with the only edge connected to it.

Saki is curious about how much waste will be made on a given tree with nodes numbered from $$$0$$$ to $$$N-1$$$, so she will perform the following action for each $$$k=0, \cdots, N-1$$$.

1. Assign label $$$(u+k) \mod N$$$ to the node numbered $$$u$$$.
2. Record the waste $$$W_k = (\text{the waste of the current labelling})$$$.

Saki is very busy, so she has asked you for a favor. Write a program to help Saki compute $$$W_k$$$ for each $$$0 \le k \lt N$$$.

Saki successfully intercepted the secret communication of queerats, but the information is encrypted.

It is known that, for some unknown primes $$$p$$$ and $$$q$$$ with $$$2^{100} \le p, q \lt 2^{150}$$$ such that $$$2p-1$$$ and $$$2p^2-2p+1$$$ are both primes, queerats uses $$$N = p(2p-1)(2p^2-2p+1)q^2$$$ to encrypt their message.

Whether Saki can decrypt the message or not depends on whether she can recover $$$p$$$ and $$$q$$$. Write a program to help Saki recover $$$p$$$ and $$$q$$$ given $$$N$$$. Your solution will be tested against exactly 50 fixed testcases, including the sample tests.