当前没有测试数据。

Description

牛牛刚刚学习了指数函数，他好奇指数函数增长究竟有快，于是尝试在草稿纸上写下了 $x^x$ 个 $a$。而这一幕恰好被路过的小红看到了，而小红一眼就注意到了由这 $x^x$ 个 $a$ 组成的数被 $b$ 整除。牛牛感觉很神奇，小红是怎么一眼就注意到的呢？于是牛牛向你发出了求助。

Format

Input

多组测试数据。

第一行一个正整数 $t(1\le t\le 10^3)$ 表示测试数据组数。

对于每组测试数据：

一行三个正整数分别表示 $x,a,b(0\le a\le 9,1\le x,b\le 10^9)$。

Output

共 $t$ 行，若了由这 $x^x$ 个 $a$ 组成的数被 $b$ 整除，输出 Yes，反之输出 No。

Samples

123 500

623

Note

牛客小白月赛 E

2025 zstu 校赛 mid