Background

Japan, located on the convergent boundary where the Pacific Plate and the Eurasian Plate disappear, is one of the countries in the world where earthquakes occur most frequently. On March 11, 2011, at 2:46:18 PM Japan time, a magnitude 9 earthquake struck the country, followed by a massive tsunami more than 10 meters high. Families torn apart and countless deaths are the best description of this tragic event.

In May 2011, ZUN, the creator of Touhou Project, composed an album for the disaster victims of the earthquake, titled "Unknown Flower, Meiji Journey", and all the proceeds raised were donated for disaster relief.

---

In the near-future scientific century, Renko and Merry talked about this great earthquake again during a chat. This earthquake also severely damaged traditional religions: thousands of shrines were damaged to varying degrees, and many shrines had their main halls completely or partially destroyed. Even the Hakurei Shrine in the Outside World was destroyed because of it.

Renko and Merry decided to set off for the Hakurei Shrine in the Outside World, enter Gensokyo, and report this news.

Problem Description

Brief Statement

A positive integer sequence of length $n$ is called "$k$-good" if and only if it satisfies the following conditions:

• For $1< i< n$, the largest among $a_{i-1},a_i,a_{i+1}$ equals the sum of the other two.
• All elements are not less than $k$.

There are $T$ queries. Each query gives $(a_0,a_1,x,y,k)$. Determine whether there exists a "$k$-good" sequence (with length at least $2$) whose first two terms are $a_0,a_1$, and that contains two adjacent terms equal to $x,y$ in order.

---

Original Statement

The already deserted Hakurei Shrine became even more desolate after the earthquake. Renko and Merry hurried to the Hakurei Shrine and only saw the collapsed torii gate. Since the shrine was too deserted, they decided to clean it up properly before entering Gensokyo.

Specifically, there are some objects in the shrine waiting to be organized, and each object has a positive integer charm value. You may assume that there are enough objects of each charm value. From the abandoned ema, Renko learned that the objects in the Hakurei Shrine before it was destroyed by the earthquake should have the following characteristics:

• Each object has a charm value not less than $k$.
• The maximum charm value among any three adjacent objects is the sum of the charm values of the other two objects.
• The charm values of the first two objects are $a_0, a_1$, respectively.
• There exist two adjacent objects whose charm values are $x, y$ in order.

Renko and Merry believe that if they can select some objects and arrange them to satisfy the characteristics above, then the shrine is beautiful, and they will not get exorcised by Reimu as soon as they enter Gensokyo.

Obviously, due to the loss of the objects, Renko and Merry may not be able to make the shrine beautiful using this information. They came to you and hope you can tell them whether, under these rules, there exists a way to make the shrine beautiful.

Because Reimu exorcises too harshly, they worry about their safety, so they will ask you $T$ times to make sure you are not fooling them.

Input Format

The first line contains a positive integer $T$, denoting the number of test cases. For each test case:

• Each line contains $5$ positive integers separated by spaces: $a_0,a_1,x,y,k$, with meanings as described in the statement.

Output Format

• For each test case, output one line containing yes or no, indicating whether there exists a way to make the shrine beautiful.

5
2 3 7 9 1
4 9 2 5 1
4 9 2 5 2
6 4 1 2 3
7 9 7 9 7

yes
yes
no
no
yes

Hint

Explanation of Samples

• For the first query, $a_0=2,a_1=3$. Renko and Merry can construct the objects as: $2,3,5,2,7,9,2,11,\dots$, where $a_5=7,a_6=9$, so there exists a way to make the shrine beautiful.
• For the second query, $a_0=4,a_1=9$. Renko and Merry can construct the objects as: $4,9,5,4,1,3,2,5,3,8,\dots$, where $a_6=2,a_7=5$, so there exists a way to make the shrine beautiful.
• For the third query, since $a_i \geq k=2$ is required, the method in the second query no longer works, and it can also be proven that there is no way to make the shrine beautiful.
• For the fourth query, it requires that the constructed $x=1,y=2$ are both less than or equal to $3$, so the shrine cannot be made beautiful.
• For the fifth query, obviously $a_0=7,a_1=9$ already satisfies the requirement for making the shrine beautiful.

Constraints

This problem uses bundled test cases.

Let $n=\max(a_0,a_1,x,y,k)$.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{Score}} & \bm{T\le } & \bm{n\le } & \textbf{\textsf{Special Property}} & \textbf{Subtask \textsf{Dependencies}}\cr\hline 1 & 10 & 10 & 10 & - & - \cr\hline 2 & 20 & 300 & 1000 & \mathbf{A} & - \cr\hline 3 & 10 & 300 & 10^9 & \mathbf{B} & - \cr\hline 4 & 20 & 300 & 10^8 & \mathbf{C} & 1,2 \cr\hline 5 & 40 & 10^5 & 10^9 & - & 3,4 \cr\hline \end{array}$$

• Special property $\mathbf{A}$: $k$ is the same for every query.
• Special property $\mathbf{B}$: $k=1$.
• Special property $\mathbf{C}$: $\sum n \leq 10^8$.

For $100\%$ of the data, $1 \leq n \leq 10^9,1 \leq T \leq 10^5$.

Translated by ChatGPT 5