素数判断(Miller-Rabin模板)

题目描述

给定 $n$ 以及 $n$ 个正整数,请你判断这 $n$ 个正整数是否为质数,对于第 $i$ 个正整数,如果它是质数输出"Yes" ,否则输出 "No" (不含引号)。

输入输出格式

输入格式


第一行一个整数:$n$ ($n <= 10000$) 第 $2$ 到第 $n + 1$ 行,每行一个整数 $x$,表示需要判断的正整数。

输出格式


一共 $i$ 行。 对于第 $i$ 个正整数,如果它是质数在第 $i$ 行输出"Yes" ,否则输出 "No" (不含引号)。

输入输出样例

输入样例 #1

5
1
2
3
4
5

输出样例 #1

No
Yes
Yes
No
Yes

说明

$30$% 的数据保证: $n <= 7000$ 并且 $x <= 10^9$ $100$% 的数据保证: $n <= 10000$ 并且 $x <= 10^{18}$ (具体数据会根据 $x$ 的值进行调整,保证常数正常的 $Miller Rabin$ 算法可以通过本题) 数据已经放入了 [卡米切尔数](https://baike.baidu.com/item/%E5%8D%A1%E8%BF%88%E5%85%8B%E5%B0%94%E6%95%B0/9083263?fr=aladdin&fromid=100223&fromtitle=%E5%8D%A1%E7%B1%B3%E5%88%87%E5%B0%94%E6%95%B0),请勿试图用费马小定理过掉本题。