#1211. Rectangle Cutting

Rectangle Cutting

题目描述

  • 翁老师有一个大小为 a×ba \times b 的长方形。他尝试将这个长方形切成 两个边长为整数 的长方形,切口 平行于 原长方形的一条边。然后,翁老师试图用这两个长方形拼成 另一个 长方形,他可以随意旋转和移动这两个长方形。请注意必须保证可以拼成一个长方形,而不是拼成一个不规则图形。
  • 请注意,如果两个长方形仅有 9090^{\circ} 旋转的区别,那么它们就被视为 相同 的长方形。例如,长方形 6×46 \times 44×64 \times 6 被认为是相同的。
  • 因此,从 2×62 \times 6 长方形可以形成另一个长方形,因为它可以切割成两个 2×32 \times 3 长方形,然后用这两个长方形形成 4×34 \times 3 长方形,它与 2×62 \times 6 长方形不同。

  • 但是,从 2×12 \times 1 长方形中却不能形成另一个长方形,因为它只能被切割成两个 1×11 \times 1 长方形,而从这两个长方形中只能形成 1×21 \times 22×12 \times 1 长方形,这两个长方形被认为是相同的。

  • 帮助翁老师确定他是否能得到其他长方形,若可以切割后拼成和原来不同的长方形,输出 Yes 否则输出 No

为了防止轻易的输出 YesNo 而骗到分数,我们给本题提供了 tt 组询问。但也不要灰心,本题我们会设置部分分,你可以看数据范围来为你提供做题的思路。

输入格式

第一行输入一个数字 tt 代表 tt 组询问。

接下来 tt 行,每行输入两个数字 a,ba,b 空格隔开。

输出格式

一共输出 tt 行,每行输入一个字符串,要么是 Yes 要么是 No

7
1 1
2 1
2 6
3 2
2 2
2 4
6 3
No
No
Yes
Yes
Yes
Yes
No

提示

在第一个测试案例中,1×11×1 长方形无法切割成两个长方形,因此无法从中得到另一个长方形。

在第四个测试案例中,3×23×2 长方形可以切割成两个 3×13×1 长方形,并由此形成 1×61×6 长方形。

在第五个测试案例中,2×22×2 长方形可以切割成两个 1×21×2 长方形,并由此形成 1×41×4 长方形。

数据范围

对于 10%10\% 的数据范围,保证 t=1t=1a,ba,b 都是 11

对于 30%30\% 的数据范围,保证 t1000t\leq 1000a,ba,b 都是奇数,a,ba,b 的最大值不超过 10001000

对于 100%100\% 的数据范围,保证 t105t\leq 10^51a,b1091\leq a,b\leq 10^9