Consider the following expression: $$$$$$\sqrt{a_1} \pm \sqrt{a_2} \pm \dots \pm \sqrt{a_n} = 0\text{.}$$$$$$ Calculate the number of ways to replace each $$$\pm$$$ with $$$+$$$ or $$$-$$$ so that it holds true.

You are given an integer array $$$a_1, \dots, a_n$$$ and an integer array $$$b_1, \dots, b_n$$$.

You have to calculate the array $$$c_1, \dots, c_{n}$$$ defined as follows:

$$$$$$c_k = \max\limits_{\gcd(i,j) = k} |a_i - b_j|\text{.}$$$$$$

It becomes more and more popular to share something instead of buying it.

One of the promising sharing systems is money sharing. There are numerous approaches to it, but we will deal with the one when there is a public entry point where money may be borrowed or returned free of charge. No need to say that the system quickly rose to be extremely popular.

Due to such popularity, it is hard to keep the system stable, so one has to request borrowing some money several days in advance. You are to develop an automatic managing system for money sharing. Consider a single day: during the day, you have $$$n$$$ requests for money lending, and there are also $$$m$$$ resupplies scheduled. They both may be described by non-zero integer $$$x$$$. Initially, the entry point has no money. On event described by $$$x$$$:

• If $$$x \gt 0$$$, then it is a resupply, so the amount of money in the entry point is increased by $$$x$$$.
• If $$$x \lt 0$$$, then it is a request to borrow the amount of money equal to $$$|x|$$$. If the request is approved, then the amount of money in the entry point is decreased by $$$|x|$$$. Otherwise, it does not change.

Unfortunately, it is not always possible to satisfy all requests, because the entry point may eventually end up not having enough money to lend, so some requests may have to be declined. Your task is, given the description of all requests and resupplies, to choose for each request whether to accept or decline it, so that the entry point always has enough money to satisfy the accepted requests. If there are multiple possible answers, you should choose the one having the minimum possible number of requests declined. If there are still multiple possible answers, find any one of them.

Consider the sequence of strings $$$F_1, F_2, \dots$$$, defined as:

$$$$$$ F_1 = ab\text{,} $$$$$$ $$$$$$ F_{k+1} = F_kF_kb\text{.} $$$$$$

Calculate the number of distinct subsequences of the string $$$F_{n}$$$ modulo $$$10^9+7$$$.

Consider the following constant: $$$$$$\varphi = \dfrac{9}{10} \cdot \dfrac{99}{100} \cdot \dfrac{999}{1000} \cdot \dfrac{9999}{10000}\cdot \dots$$$$$$

You have to find the $$$n$$$-th digit after the decimal separator in the decimal representation of $$$\varphi$$$.

Consider two sets of $$$n$$$ lines passing through the point $$$(0;0;0)$$$ in Euclidean three-dimensional space. Instead of actual lines, you are given two sets, $$$2n$$$ points in each set: $$$r_i=(x_i;y_i;z_i)$$$ and $$$r_j'=(x_j';y_j';z_j')$$$. These are the points where the lines intersect the unit sphere (two opposite points for each line).

It is known that the second set was obtained from the first one by some rotation around the origin and shuffling the order of the points. You have to find a permutation $$$\pi_1, \dots, \pi_{2n}$$$ and the rotation $$$\varphi$$$ of three-dimensional space such that, for all $$$i$$$, $$$$$$|r_{\pi_i} - \varphi(r'_i)| \leq 10^{-6}\text{.}$$$$$$ The rotation $$$\varphi$$$ should be described by point $$$e=(x;y;z)$$$ and angle $$$\theta$$$. It means we rotate the space around the axis from the origin to point $$$e$$$ by angle $$$\theta$$$ following the right-hand rule (see notes).

It is guaranteed that the directions of the first set of lines were chosen uniformly at random, independently from each other.

Planet Oz is located in the origin of two-dimensional euclidean space. Elphaba wants to show everyone that her powers lie far beyond the laws of physics. To do this, she wants to take off from Oz and fly away along some straight line to infinity and beyond.

The task is complicated by the fact that Oz has $$$n$$$ satellites revolving around it. For each satellite, its polar coordinates $$$(\rho_i; \varphi_i)$$$ and mass $$$m_i$$$ are known. Here, the planet and satellites are considered points, $$$\rho_i$$$ is the radial distance from Oz to the $$$i$$$-th satellite, and $$$\varphi_i$$$ is the polar angle between the satellite and some fixed reference direction measured in arc seconds.

Assume that Elphaba is located in the point denoted by vector $$$\vec r$$$ and has mass $$$m$$$, while $$$i$$$-th satellite is located in the point denoted by vector $$$\vec r_i$$$. The satellite attracts Elphaba with the force directed from Elphaba to the satellite. This force is proportional to Elphaba's mass $$$m$$$ and satellite's mass $$$m_i$$$, and inversely proportional to the squared distance between them, $$$|\vec r - \vec r_i|^2$$$. Thus, exact value of force $$$\vec F_i$$$ applied to Elphaba by $$$i$$$-th satellite is as follows:

$$$$$$\vec F_i = -\dfrac{Gmm_i(\vec r - \vec r_i)}{|\vec r - \vec r_i|^3}$$$$$$

Here, $$$G$$$ is the universal gravitational constant, the value of which does not concern us in this problem.

Forces applied from different satellites sum up directly. Therefore, the overall force $$$\vec F$$$ applied to Elphaba by all satellites is equal to $$$\vec F = \vec F_1 + \dots + \vec F_n$$$.

Elphaba wants to choose the direction of her flight in such a way that it doesn't pass through any of the satellites, and its direction is not affected by satellites at any moment of time. In other words, the force $$$\vec F$$$ must be collinear to $$$\vec r$$$ for all points $$$\vec r$$$ on Elphaba's trajectory.

Your task is to find all possible directions for Elphaba's flight.

This is an interactive problem.

Someone picked a positive rational number $$$x=p/q$$$ where $$$1 \leq p, q \leq 10^9$$$. You may ask at most $$$10$$$ queries of the kind "? $$$m$$$", where $$$10^9 \lt m \lt 10^{12}$$$ and $$$m$$$ is a prime number. For each query, you will get the number $$$y$$$ such that $$$y \equiv pq^{-1} \pmod{m}$$$. You have to guess the number $$$x$$$.

The first line of input contains a single integer $$$t$$$, the number of test cases ($$$1 \leq t \leq 10^5$$$).

For each test case, you may ask at most $$$10$$$ queries. Each query should be one of two types:

1. "? $$$m$$$", where $$$10^9 \lt m \lt 10^{12}$$$ and $$$m$$$ is a prime number,
2. "! $$$p$$$ $$$q$$$", where $$$1 \leq p, q \leq 10^9$$$, meaning that the answer is equal to $$$p/q$$$.

Let $$$T$$$ be a tree on $$$n$$$ vertices. We call permutation $$$\pi = \pi_1, \pi_2, \dots, \pi_n$$$ an automorphism of $$$T$$$ if, for any pair of vertices $$$(u, v)$$$, there is an edge between them if and only if there is an edge between $$$\pi_u$$$ and $$$\pi_v$$$.

Let $$$\alpha=\alpha_1, \alpha_2, \dots, \alpha_n$$$ and $$$\beta=\beta_1,\beta_2,\dots,\beta_n$$$ be two permutations. Then their composition $$$\gamma = \alpha \circ \beta$$$ is defined as $$$\gamma = \alpha_{\beta_1}, \alpha_{\beta_2}, \dots, \alpha_{\beta_n}$$$, that is, $$$\gamma_i = \alpha_{\beta_i}$$$. Automorphisms of $$$T$$$ are closed under composition, so if $$$\alpha$$$ and $$$\beta$$$ are two automorphisms of $$$T$$$, then $$$\alpha \circ \beta$$$ is its automorphism as well. Indeed, it may be conceived as if we firstly applied automorphism $$$\beta$$$ and then automorphism $$$\alpha$$$.

You have to find a set of automorphisms $$$P=\{\pi^{(1)}, \pi^{(2)}, \dots, \pi^{(k)}\}$$$ such that $$$k \lt n$$$ and any automorphism of $$$T$$$ may be represented as finite composition of permutations from $$$P$$$.