310297: CF1811D. Umka and a Long Flight

D. Umka and a Long Flighttime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The girl Umka loves to travel and participate in math olympiads. One day she was flying by plane to the next olympiad and out of boredom explored a huge checkered sheet of paper.

Denote the $n$-th Fibonacci number as $F_n = \begin{cases} 1, & n = 0; \\ 1, & n = 1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{cases}$

A checkered rectangle with a height of $F_n$ and a width of $F_{n+1}$ is called a Fibonacci rectangle of order $n$.

Umka has a Fibonacci rectangle of order $n$. Someone colored a cell in it at the intersection of the row $x$ and the column $y$.

It is necessary to cut this rectangle exactly into $n+1$ squares in such way that

• the painted cell was in a square with a side of $1$;
• there was at most one pair of squares with equal sides;
• the side of each square was equal to a Fibonacci number.

Will Umka be able to cut this rectangle in that way?

Input

The first line contains an integer $t$ ($1 \le t \le 2 \cdot 10^5$) — number of test cases.

For each test case the integers $n$, $x$, $y$ are given ($1 \le n \le 44$, $1 \le x \le F_n$, $1 \le y \le F_{n+1}$) — the order of the Fibonacci rectangle and the coordinates of the colored cell.

Output

For each test case, print "YES" if the answer is positive, and "NO" otherwise.

You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive answer).

ExampleInput

12
1 1 1
2 1 2
3 1 4
3 3 2
4 4 6
4 3 3
5 6 5
5 4 12
5 2 12
4 2 1
1 1 2
44 758465880 1277583853

Output

YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO

Note The first, third and fourth test cases.

题目大意：
乌姆卡喜欢旅行和参加数学奥林匹克。有一天，她乘坐飞机去参加下一个奥林匹克，在无聊中研究了一张巨大的棋盘纸。

将第n个斐波那契数记为$F_n = \begin{cases} 1, & n = 0; \\ 1, & n = 1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{cases}$

一个高度为$F_n$，宽度为$F_{n+1}$的棋盘矩形被称为第n个斐波那契矩形。

乌姆卡有一个第n个斐波那契矩形。有人在其中一格交叉的行x和列y上涂了颜色。

必须将这个矩形**恰好**切成n+1个正方形，使得：
- 涂色的单元格在一个边长为1的正方形中；
- 最多只有一对边长相等的正方形；
- 每个正方形的边长都等于一个斐波那契数。

乌姆卡能够以这种方式切割这个矩形吗？

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤2×10^5）——测试用例的数量。
对于每个测试用例，给出整数n，x，y（1≤n≤44，1≤x≤F_n，1≤y≤F_{n+1}）——斐波那契矩形的顺序和涂色单元格的坐标。

输出：
对于每个测试用例，如果答案为肯定，则输出“YES”，否则输出“NO”。
“YES”和“NO”可以任何大小写打印（例如，“yEs”，“yes”和“Yes”都将被视为肯定答案）。题目大意： 乌姆卡喜欢旅行和参加数学奥林匹克。有一天，她乘坐飞机去参加下一个奥林匹克，在无聊中研究了一张巨大的棋盘纸。 将第n个斐波那契数记为$F_n = \begin{cases} 1, & n = 0; \\ 1, & n = 1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{cases}$ 一个高度为$F_n$，宽度为$F_{n+1}$的棋盘矩形被称为第n个斐波那契矩形。 乌姆卡有一个第n个斐波那契矩形。有人在其中一格交叉的行x和列y上涂了颜色。 必须将这个矩形**恰好**切成n+1个正方形，使得： - 涂色的单元格在一个边长为1的正方形中； - 最多只有一对边长相等的正方形； - 每个正方形的边长都等于一个斐波那契数。 乌姆卡能够以这种方式切割这个矩形吗？ 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤2×10^5）——测试用例的数量。 对于每个测试用例，给出整数n，x，y（1≤n≤44，1≤x≤F_n，1≤y≤F_{n+1}）——斐波那契矩形的顺序和涂色单元格的坐标。 输出： 对于每个测试用例，如果答案为肯定，则输出“YES”，否则输出“NO”。 “YES”和“NO”可以任何大小写打印（例如，“yEs”，“yes”和“Yes”都将被视为肯定答案）。