No testdata at current.

问题描述

塔子哥是一位对数学有着浓厚兴趣的程序员。最近,他在研究无限循环小数时遇到了一个有趣的问题。对于循环节长度为 $k$ 的无限循环小数,塔子哥想要判断它是否可以写成分数 $\frac{a}{p}$ 的形式。

无限循环小数是指小数部分从某一位置开始,数字按固定的顺序循环出现。这个循环出现的数字序列就称为循环节。例如,无限循环小数 $0.142857142857\ldots$ 的循环节长度为 $6$。

塔子哥需要你的帮助来解决这个问题。他会给出一系列询问,每次询问包含两个正整数 $k$ 和 $p$,你需要判断是否存在分子 $a$,使得分数 $\frac{a}{p}$ 的小数部分是一个循环节长度为 $k$ 的无限循环小数。

输入格式

第一行包含一个正整数 $q$,表示询问的次数。

接下来 $q$ 行,每行包含两个正整数 $k$ 和 $p$,分别表示循环节的长度和被询问的分母。

输出格式

输出共 $q$ 行,对于每一个询问,如果存在分子 $a$,使得分数 $\frac{a}{p}$ 的小数部分是一个循环节长度为 $k$ 的无限循环小数,则输出 Yes,否则输出 No。

样例输入

5
1 6
2 4
3 37
100000 3
2 37

样例输出

Yes
No 
Yes
Yes
No

样例解释

第一个询问: $\frac{1}{6} = 0.166666\ldots$,循环节长度为 $1$,因此输出 Yes。

第二个询问: 分母为 $4$ 的分数都是有限小数,不存在循环节,因此输出 No。

第三个询问: $\frac{8}{37} = 0.216216\ldots$,循环节长度为 $3$,因此输出 Yes。

第四个询问: $\frac{1}{3} = 0.333\ldots$,循环节长度为 $1$,尽管循环节长度为 $100000$,但仍然满足要求,因此输出 Yes。

第五个询问: 不存在分子 $a$,使得 $\frac{a}{37}$ 的小数部分是一个循环节长度为 $2$ 的无限循环小数,因此输出 No。

评测数据与规模

对于所有评测用例,满足 $1 \leq q \leq 10^5, 1 \leq k, p \leq 10^9$。