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_ 包含多个 _round_。规则非常简单：在每一轮中，会选出一个自然数 #cf_span[k]。然后，更快说出（或吠出）该数字的一方赢得该 _round_。之后，赢家的分数乘以 #cf_span[k2]，输家的分数乘以 #cf_span[k]。游戏开始时，Slastyona 和 Pushok 的分数均为 1。
不幸的是，Slastyona 失去了记录所有 #cf_span[n] 个 _games_ 历史的笔记本。不过，她仍能回忆起每个游戏的最终结果，但这些记忆都很模糊。请帮助 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 rounds of a game, where $ m \geq 0 $ is the number of rounds.
Let $ S \subseteq \{1, \dots, m\} $ be the set of indices of rounds won by Slastyona, and $ P = \{1, \dots, m\} \setminus S $ be the set of indices of rounds won by Pushok.
Initial scores: $ s_0 = 1 $, $ p_0 = 1 $.
After round $ j $:
- If Slastyona wins: $ s \leftarrow s \cdot k_j $, $ p \leftarrow p \cdot k_j $
- If Pushok wins: $ p \leftarrow p \cdot k_j $, $ s \leftarrow s \cdot k_j $
Thus, after all rounds:
$$
s = \prod_{j=1}^m k_j, \quad p = \prod_{j=1}^m k_j
$$
**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 multiset of positive integers $ \{k_1, k_2, \dots, k_m\} $ such that:
$$
a_i = \prod_{j=1}^m k_j \quad \text{and} \quad b_i = \prod_{j=1}^m k_j
$$
That is, determine whether $ a_i = b_i $.
API Response (JSON)
{
"problem": {
"name": "A. 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": "CF833A"
},
"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_ 包含多个 _round_。规则非常简单：在每一轮中，会选出一个自然数 #cf_span[k]。然后，更快说出（或吠出）该数字的一方赢得该 _round_。之后，赢家的分数乘以 #cf_span[k2]，输家的分数乘以 #cf_span[k]。游戏开始时，Slastyona 和 Pu...",
"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"
}
]
}