English · Original
Chinese · Translation
Formal · Original
<center></center>Slastyona and her loyal dog Pushok are playing a meaningless _game_ that is indeed very interesting.
The _game_ consists of multiple _rounds_. Its rules are very simple: in each round, a natural number _k_ is chosen. Then, the one who says (or barks) it faster than the other wins the _round_. After that, the winner's score is multiplied by _k_2, and the loser's score is multiplied by _k_. In the beginning of the _game_, both Slastyona and Pushok have scores equal to one.
Unfortunately, Slastyona had lost her notepad where the history of all _n_ _games_ was recorded. She managed to recall the final results for each games, though, but all of her memories of them are vague. Help Slastyona verify their correctness, or, to put it another way, for each given pair of scores determine whether it was possible for a game to finish with such result or not.
## Input
In the first string, the number of games _n_ (1 ≤ _n_ ≤ 350000) is given.
Each _game_ is represented by a pair of scores _a_, _b_ (1 ≤ _a_, _b_ ≤ 109) – the results of Slastyona and Pushok, correspondingly.
## Output
For each pair of scores, answer "_Yes_" if it's possible for a game to finish with given score, and "_No_" otherwise.
You can output each letter in arbitrary case (upper or lower).
[samples]
## Note
First _game_ might have been consisted of one round, in which the number 2 would have been chosen and Pushok would have won.
The second _game_ needs exactly two rounds to finish with such result: in the first one, Slastyona would have said the number 5, and in the second one, Pushok would have barked the number 3.
Slastyona 和她忠诚的狗 Pushok 正在玩一个毫无意义但确实非常有趣的 _game_。
该 _game_ 包含多轮。规则非常简单：在每一轮中，会选出一个自然数 #cf_span[k]。然后，更快说出（或吠出）该数字的一方赢得该轮。之后，获胜者的分数乘以 #cf_span[k2]，失败者的分数乘以 #cf_span[k]。游戏开始时，Slastyona 和 Pushok 的分数均为 1。
不幸的是，Slastyona 失去了记录所有 #cf_span[n] 场 _game_ 历史的笔记本。不过，她还记得每场游戏的最终结果，但对这些结果的记忆都很模糊。请帮助 Slastyona 验证这些结果的正确性，或者说，对于每组给定的分数，判断是否存在一种可能的游戏过程，使得游戏以该结果结束。
第一行给出游戏场数 #cf_span[n] #cf_span[(1 ≤ n ≤ 350000)]。
每场 _game_ 由一对分数 #cf_span[a], #cf_span[b] #cf_span[(1 ≤ a, b ≤ 109)] 表示，分别代表 Slastyona 和 Pushok 的最终得分。
对于每对分数，如果存在一种可能的游戏过程使得游戏以该分数结束，则输出 "_Yes_"，否则输出 "_No_"。
你可以以任意大小写形式输出每个字母。
第一场 _game_ 可能只包含一轮，其中选出的数字为 #cf_span[2]，且 Pushok 获胜。
第二场 _game_ 需要恰好两轮才能得到该结果：第一轮中，Slastyona 说出了数字 #cf_span[5]，第二轮中，Pushok 吠出了数字 #cf_span[3]。
## Input
第一行给出游戏场数 #cf_span[n] #cf_span[(1 ≤ n ≤ 350000)]。每场 _game_ 由一对分数 #cf_span[a], #cf_span[b] #cf_span[(1 ≤ a, b ≤ 109)] 表示，分别代表 Slastyona 和 Pushok 的最终得分。
## Output
对于每对分数，如果存在一种可能的游戏过程使得游戏以该分数结束，则输出 "_Yes_"，否则输出 "_No_"。你可以以任意大小写形式输出每个字母。
[samples]
## Note
第一场 _game_ 可能只包含一轮，其中选出的数字为 #cf_span[2]，且 Pushok 获胜。第二场 _game_ 需要恰好两轮才能得到该结果：第一轮中，Slastyona 说出了数字 #cf_span[5]，第二轮中，Pushok 吠出了数字 #cf_span[3]。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of games.
For each game $ i \in \{1, \dots, n\} $, let $ (a_i, b_i) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $ denote the final scores of Slastyona and Pushok, respectively.
Let $ k_1, k_2, \dots, k_m \in \mathbb{Z}^+ $ be a sequence of natural numbers chosen in the $ m $ rounds of a game.
For each round $ j \in \{1, \dots, m\} $, one player wins and their score is multiplied by $ k_j $, while the other’s score is multiplied by $ k_j $ as well.
Initially, both players have score 1.
**Constraints**
1. $ 1 \leq n \leq 350000 $
2. For each game $ i $: $ 1 \leq a_i, b_i \leq 10^9 $
**Objective**
For each game $ i $, determine whether there exists a finite sequence of natural numbers $ k_1, \dots, k_m $ and an assignment of winners per round (Slastyona or Pushok), such that:
$$
a_i = \prod_{j=1}^m k_j^{w_j}, \quad b_i = \prod_{j=1}^m k_j^{1 - w_j}
$$
where $ w_j \in \{0, 1\} $ indicates whether Slastyona won round $ j $ (1) or not (0).
Equivalently, define $ P = \prod_{j=1}^m k_j $. Then:
$$
a_i \cdot b_i = P^2
$$
and both $ a_i $ and $ b_i $ must divide $ P $.
Thus, the condition is:
$$
a_i \cdot b_i \text{ is a perfect square}, \quad \text{and} \quad \gcd(a_i, b_i)^2 \mid a_i \cdot b_i
$$
But since $ \gcd(a_i, b_i)^2 \mid a_i b_i $ always holds when $ a_i b_i $ is a square, the **only necessary and sufficient condition** is:
$$
a_i \cdot b_i \text{ is a perfect square}
$$
**Answer for each game $ i $:**
$$
\boxed{\text{Yes}} \quad \text{if and only if} \quad a_i \cdot b_i \text{ is a perfect square}
$$
$$
\boxed{\text{No}} \quad \text{otherwise}
$$
API Response (JSON)
{
"problem": {
"name": "C. The Meaningless Game",
"description": {
"content": "<center></center>Slastyona and her loyal dog Pushok are playing a meaningless _game_ that is indeed very interesti",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF834C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "<center></center>Slastyona and her loyal dog Pushok are playing a meaningless _game_ that is indeed very interesti...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Slastyona 和她忠诚的狗 Pushok 正在玩一个毫无意义但确实非常有趣的 _game_。\n\n该 _game_ 包含多轮。规则非常简单：在每一轮中，会选出一个自然数 #cf_span[k]。然后，更快说出（或吠出）该数字的一方赢得该轮。之后，获胜者的分数乘以 #cf_span[k2]，失败者的分数乘以 #cf_span[k]。游戏开始时，Slastyona 和 Pushok 的分数均为 1...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of games. \nFor each game $ i \\in \\{1, \\dots, n\\} $, let $ (a_i, b_i) \\in \\mathbb{Z}^+ \\times \\mathbb{Z}^+ $ denote the final scores of Slastyo...",
"is_translate": false,
"language": "Formal"
}
]
}