1412: 土拨鼠之谜
Memory Limit：128 MB
Time Limit：1.500 S
Judge Style：Text Compare
Creator：
Submit：145
Solved：12
Description
一只土拨鼠做了一个梦，梦里奇怪而又恶意的文字裹挟着它。
从梦中惊醒，它再也睡不下去，早早开始这一天。
这天入夜，土拨鼠早早睡了，但梦境却没有一点变化，同样的梦，同样的惊醒，同样的这一天...
无论土拨鼠如何挣扎，这一天依旧不会停止。
无止境的今天让土拨鼠逐渐疯狂，却也因此读懂了梦中的文字:”答案就在..."。
原来，土拨鼠的这一天和它的命运刚开始是同一个无前缀零的四位数$a$，每一次轮回，土拨鼠的尝试都将使它的”这一天“乘上它的命运。
换而言之，土拨鼠第$i$天的的情况可以用$a^i$表示
梦中的文字告诉他，当一天末尾关键的四位数依序组成的数值是$b$时，就能逃出轮回。
但是，土拨鼠的理智只能支撑它走到第$n$天，请问它能否在$n$天之内逃出轮回？
从梦中惊醒，它再也睡不下去，早早开始这一天。
这天入夜，土拨鼠早早睡了，但梦境却没有一点变化，同样的梦，同样的惊醒，同样的这一天...
无论土拨鼠如何挣扎，这一天依旧不会停止。
无止境的今天让土拨鼠逐渐疯狂，却也因此读懂了梦中的文字:”答案就在..."。
原来，土拨鼠的这一天和它的命运刚开始是同一个无前缀零的四位数$a$，每一次轮回，土拨鼠的尝试都将使它的”这一天“乘上它的命运。
换而言之，土拨鼠第$i$天的的情况可以用$a^i$表示
梦中的文字告诉他，当一天末尾关键的四位数依序组成的数值是$b$时，就能逃出轮回。
但是，土拨鼠的理智只能支撑它走到第$n$天，请问它能否在$n$天之内逃出轮回？
Input
第一行，一个整数$t$,代表测试组数
接下来$t$行，每行三个整数$n$,$a$,$b$
数据范围：
$1 \le t \le 10000$
$1 \le n \le 10^9$
$1000 \le a \le 9999$
$0 \le b \le 9999$
接下来$t$行，每行三个整数$n$,$a$,$b$
数据范围：
$1 \le t \le 10000$
$1 \le n \le 10^9$
$1000 \le a \le 9999$
$0 \le b \le 9999$
Output
$t$行，每行一个字符串，如果可以逃出轮回，输出”YES",否则输出"NO"
Sample Input Copy
5
10 1001 2
1000000000 1001 2
5 2345 625
100 1001 3
100 1002 8688
Sample Output Copy
NO
NO
YES
NO
YESHINT
第三个样例中，$2345^4=30239275950625$，末尾四位数组成的数为625
第五个样例中，土拨鼠在第99天逃出了轮回
第五个样例中，土拨鼠在第99天逃出了轮回