Battle of Brains (BoB) is the yearly programming contest among students of the University of Dhaka. Only first and second year students of DU (any department or institute) can take part in the contest. The sole purpose of this contest is to spark an interest in the realm of problem solving in the mind of the freshers and sophomores.

In CSEDU lab, there are two computers on each table. Two contestants may communicate if they are classmates and sit at the same table. But communication is not allowed between contestants since this is an individual contest. So the organizers planned not to seat two classmates at the same table. After all the contestants arrive, the volunteers are going to seat two contestants from two different years at each table. An interesting fact is that every year the number of first-year contestants is larger than the number of second-year contestants. So after a while, some contestants are still standing there and all are first-year students.

The volunteers count the total number of contestants and the number of first-year students who are still standing there.

Now you will be given the total number of contestants and the number of first-year contestants who are still standing there. Your task is to find the number of contestants from first-year and the number of contestants from second-year.

It is guaranteed that the given data is valid according to the aforementioned scenario.

You are given an array $$$A$$$ of $$$n$$$ integers, where the $$$i$$$-th element is $$$A_i$$$. You can choose exactly one $$$i$$$ such that $$$1 \leq i \leq n$$$ and change $$$A_i$$$ to $$$-A_i$$$ (in other words, you change the sign of $$$A_i$$$). You want to make the sum of the array even. In how many ways can you do this?

Given an integer $$$X$$$, let $$$f(X)$$$ denote the number of ordered pairs $$$(a,b)$$$ such that $$$\gcd(a,b) \times \text{lcm}(a,b) = X$$$.

A number $$$Y$$$ is beautiful if $$$f(Y)$$$ is odd.

Count the number of beautiful numbers that lie in a given range $$$[L, R]$$$.

Refer to the notes below if you don't understand some of these terms.

Alice and Bob went on an adventure, where they found a mysterious array $$$A$$$ consisting of $$$N$$$ positive integers. The $$$i$$$-th element of the array is called $$$A_i$$$.

Alice and Bob decided to play a game with this array, where each player moves in turn, and whoever can't find a valid move loses. Alice goes first. In simple words, Alice makes her move, then it is Bob's move, then it is Alice's move again, and so on. In every move, the player (whose move it is) does the following things sequentially:

1. Select any prime number $$$p$$$ such that there exists an index $$$i$$$ such that $$$p$$$ divides $$$A_i$$$. If no such prime number is found, the player immediately loses.
2. For each element $$$A_j$$$ from the array, if $$$p$$$ divides $$$A_j$$$, replace $$$A_j$$$ by $$$\dfrac{A_j}{p}$$$, else $$$A_j$$$ is kept unchanged. (Note that this part should be done for every element of the array, not just one).
3. The updated array is passed to the next player.

Jubayer is a nice and talented kid. He is a two times ICPC World Finalist. He used to utilize his time solving problems after problems. But after all those years of hard work and achievements, he decides to enjoy a tiny break from his daily routine and roam to the villages of his very own B.Baria district. So, he went to B.Baria. But he soon became very fed up as he saw he cannot go to every village in his district as there are not enough roads that can help him reach every village. Also, a weird pattern was caught to the attention of this great programmer. In his district, there are $$$n-1$$$ villages. The villages are named with natural numbers (don't ask me why, I am just a simple problem setter). For some weird reason, there is no village numbered as $$$1$$$. Villages are named from $$$2$$$ to $$$n$$$ (for example: if $$$n=5$$$ then name of the villages are $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$). And there is a road connecting the village $$$i$$$ and the village $$$j$$$ if and only if either $$$i$$$ is divisible by $$$j$$$, or $$$j$$$ is divisible by $$$i$$$.

Now, Jubayer wishes to create some new roads to extend the reachability: he wants to connect every village and roam everywhere without any hassle. But he is failing to determine the minimum number of roads that he needs to construct in order to fulfill this purpose. Now it is your turn to help this world famous programmer.

The FIFA World Cup 2022 will take place in Qatar. The organizers plan to provide a prize to random attendees at the opening game. So they chose two integers $$$a$$$ and $$$b$$$. The integer $$$a$$$ represents bitwise $$$\textbf{OR}$$$ of a set of seat numbers and $$$b$$$ represents bitwise $$$\textbf{XOR}$$$ of the same set of seat numbers. The attendees assigned to those seats will receive the prizes. The organizers want to award prizes to as many people as possible. They therefore recruited you to identify the maximum possible number of attendees who are qualified for the award as well as their seat numbers. Each seat has a unique seat number, which is a non-negative integer.

See the notes if you forgot what bitwise $$$\textbf{OR}$$$ and $$$\textbf{XOR}$$$ means.

At the beginning of the winter season in 2022, Ayon and Lagno received two colorful scarves as gifts from their mother. The scarves each have their own color patterns which can be described as a string of letters where each letter identifies as a unique color. Lagno was worried that her scarf would not match her brother's, but fortunately, she found a way to modify the colors on her own scarf.

Consider the color pattern of a scarf as a string consisting of lowercase English letters only. The pattern for Lagno's scarf is $$$S$$$ and Ayon's scarf is $$$T$$$. Both strings are of equal length $$$n$$$. For a given integer $$$k$$$, you can perform the following operation as many times as you want (maybe zero).

1. Choose two indices $$$i$$$ and $$$j$$$ such that $$$1\leq i,j\leq n$$$ and $$$\left|i-j\right|=k$$$.
2. Change $$$S[i]$$$ to $$$S[j]$$$.

Can Lagno change her string $$$S$$$ to make it equal to her brother's string $$$T$$$?

Alice and Bob are playing a game. Alice gives Bob an integer $$$k$$$. Then Bob picks another non-negative integer $$$n$$$ and performs some moves (possibly zero) on $$$n$$$. In one move, he does the following:

• If $$$k$$$ divides $$$n$$$ (i.e. $$$n\bmod k = 0$$$), then he divides $$$n$$$ by $$$k$$$. Formally, he does $$$n:=\dfrac{n}{k}$$$.
• Otherwise, he subtracts $$$1$$$ from $$$n$$$. Formally, he does $$$n:=n-1$$$.

Alice and Bob found a divine stairway when they went on an adventure to the seventh sky. As always, they decided to play a game with it. The rules of the game are following:

1. The first step is labeled by a positive integer $$$u$$$, and the labels of the following steps are increased by $$$1$$$ sequentially all the way up to $$$v$$$ which is the topmost step of the stairway.
2. Bob can not simply walk up the stairs due to its divine characteristics. But with the power of his infinity stones, he can teleport from step $$$a$$$ to step $$$b$$$ if and only if $$$a \lt b$$$ and the number of common divisors between $$$a$$$ and $$$b$$$ is $$$1$$$.
3. Bob is currently at step $$$u$$$ which they are calling hell and he must reach step $$$v$$$ which they are calling heaven to win the game.

Given a sorted array $$$A$$$ with $$$N$$$ elements (non-decreasing order), you will be given $$$Q$$$ queries. In each query, you will be given a range $$$[L, R]$$$. For each query, you have to find the number of non-negative integers $$$X$$$ such that $$$X \lt 2^{20}$$$ and after doing the following operation the whole array remains sorted (non-decreasing order):

• For each $$$i$$$ such that $$$L \le i \le R$$$, assign $$$A_i := A_i \oplus X$$$.

Note that the queries are independent. So you do not actually apply the operations on the array when you move on to the next query.