{"raw_statement":[{"iden":"statement","content":"<center>![image](https://espresso.codeforces.com/56bbfc867500f14be501051546c491da9cd00de9.png)</center>Slastyona and her loyal dog Pushok are playing a meaningless _game_ that is indeed very interesting.\n\nThe _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.\n\nUnfortunately, 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."},{"iden":"input","content":"In the first string, the number of games _n_ (1 ≤ _n_ ≤ 350000) is given.\n\nEach _game_ is represented by a pair of scores _a_, _b_ (1 ≤ _a_, _b_ ≤ 109) – the results of Slastyona and Pushok, correspondingly."},{"iden":"output","content":"For each pair of scores, answer \"_Yes_\" if it's possible for a game to finish with given score, and \"_No_\" otherwise.\n\nYou can output each letter in arbitrary case (upper or lower)."},{"iden":"example","content":"Input\n\n6\n2 4\n75 45\n8 8\n16 16\n247 994\n1000000000 1000000\n\nOutput\n\nYes\nYes\nYes\nNo\nNo\nYes"},{"iden":"note","content":"First _game_ might have been consisted of one round, in which the number 2 would have been chosen and Pushok would have won.\n\nThe 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."}],"translated_statement":[{"iden":"statement","content":"Slastyona 和她忠诚的狗 Pushok 正在玩一个无意义但确实非常有趣的 _game_。\n\n该 _game_ 包含多个 _round_。规则非常简单：在每一轮中，会选出一个自然数 #cf_span[k]。然后，更快说出（或吠出）该数字的一方赢得该 _round_。之后，赢家的分数乘以 #cf_span[k2]，输家的分数乘以 #cf_span[k]。游戏开始时，Slastyona 和 Pushok 的分数均为 1。\n\n不幸的是，Slastyona 失去了记录所有 #cf_span[n] 个 _games_ 历史的笔记本。不过，她仍能回忆起每个游戏的最终结果，但这些记忆都很模糊。请帮助 Slastyona 验证这些结果的正确性，或者说，对于每组给定的分数，判断是否存在一种可能的游戏过程，使得最终结果恰好为此分数。\n\n第一行给出游戏的数量 #cf_span[n] #cf_span[(1 ≤ n ≤ 350000)]。\n\n每个 _game_ 由一对分数 #cf_span[a], #cf_span[b] #cf_span[(1 ≤ a, b ≤ 109)] 表示，分别对应 Slastyona 和 Pushok 的最终得分。\n\n对于每对分数，若存在一种可能的游戏过程使得最终结果为此分数，则输出 \"_Yes_\"，否则输出 \"_No_\"。\n\n你可以任意大小写输出每个字母。\n\n第一个 _game_ 可能只包含一轮，其中选择的数字为 #cf_span[2]，且 Pushok 获胜。\n\n第二个 _game_ 需要恰好两轮才能得到此结果：第一轮中，Slastyona 说出了数字 #cf_span[5]；第二轮中，Pushok 吠出了数字 #cf_span[3]。"},{"iden":"input","content":"第一行给出游戏的数量 #cf_span[n] #cf_span[(1 ≤ n ≤ 350000)]。每个 _game_ 由一对分数 #cf_span[a], #cf_span[b] #cf_span[(1 ≤ a, b ≤ 109)] 表示，分别对应 Slastyona 和 Pushok 的最终得分。"},{"iden":"output","content":"对于每对分数，若存在一种可能的游戏过程使得最终结果为此分数，则输出 \"_Yes_\"，否则输出 \"_No_\"。你可以任意大小写输出每个字母。"},{"iden":"note","content":"第一个 _game_ 可能只包含一轮，其中选择的数字为 #cf_span[2]，且 Pushok 获胜。第二个 _game_ 需要恰好两轮才能得到此结果：第一轮中，Slastyona 说出了数字 #cf_span[5]；第二轮中，Pushok 吠出了数字 #cf_span[3]。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 Slastyona and Pushok, respectively.\n\nLet $ 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.\n\nLet $ 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.\n\nInitial scores: $ s_0 = 1 $, $ p_0 = 1 $.  \nAfter round $ j $:  \n- If Slastyona wins: $ s \\leftarrow s \\cdot k_j $, $ p \\leftarrow p \\cdot k_j $  \n- If Pushok wins: $ p \\leftarrow p \\cdot k_j $, $ s \\leftarrow s \\cdot k_j $\n\nThus, after all rounds:  \n$$\ns = \\prod_{j=1}^m k_j, \\quad p = \\prod_{j=1}^m k_j\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 350000 $  \n2. For each game $ i $: $ 1 \\leq a_i, b_i \\leq 10^9 $\n\n**Objective**  \nFor each game $ i $, determine whether there exists a multiset of positive integers $ \\{k_1, k_2, \\dots, k_m\\} $ such that:  \n$$\na_i = \\prod_{j=1}^m k_j \\quad \\text{and} \\quad b_i = \\prod_{j=1}^m k_j\n$$\n\nThat is, determine whether $ a_i = b_i $.","simple_statement":null,"has_page_source":false}