题目描述

给定两个用于生成数字的种子 $seed,k$，以此构造数字 $x$：

1. 令 $x=\overline{1234\cdots(seed-1)seed}$（即 $1\sim seed$ 连接起来的数字）。
2. 若 $k>0$，则 $k=k-1,seed=x$，原 $x$ 无效并跳转到 1；否则结束。

问 $x$ 是否会被某个质数 $p(2\le p\le x)$ 整除（即 $p\mid x$）。

输入格式

第一行是数组组数 $t$。

对于每组数据，每行输入两个正整数 $seed,k$。

输出格式

每行一个字符 Y（满足上述条件）或 N（不满足上述条件）。

2
1 0
2 1

N
Y

样例解释

对于第一组数据，$x=1$，显然不可能满足上述条件。

对于第二组数据，$x=123456789101112$，显然会被质数 $2$ 整除。

数据范围

对于 $40\%$ 的数据，$1\le t\le 5,1\le seed\le 10,k=0$。

对于 $100\%$ 的数据，$1\le t\le 5\times10^6,1\le seed,k\le 10^{8}$。

请使用较快的输入输出方式。本题将时限开到了 $\textbf{5000\text{ms}}$，保证单个测试点时限是 std 用时的两倍以上。