暂无测试数据。

蒜头君今天出门，在地上捡到了一个序列 $a$。

秉承着拾金不昧的原则，蒜头君在原地等待序列 $a$ 的主人回来，并将序列还给了他。

但是蒜头君十分喜欢这个序列，在等待的过程中，蒜头君拿出一个初始序列，这个初始序列的长度与序列 $a$ 的长度相等，且每个数字都为 $0$。蒜头君可以对这个初始序列进行操作。对于第 $i$ 次操作：

• 可以选定初始序列中的任意位置，将其加上 $k^i$；（$i$ 从 $0$ 开始）
• 什么也不做。

蒜头君记住了序列 $a$ 中的每个数字，现在蒜头君想将这个初始序列变为序列 $a$，你能告诉蒜头君，经过若干次操作后，初始序列能变成 $a$ 序列吗？

如果可以，则输出 ^_^；否则输出 QwQ。

输入格式

第一行输入一个正整数 $T$，表示测试的组数。

接下来输入 $T$ 组数据。

对于每组数据：

第一行输入两个整数 $n,k$，分别表示序列长度和题面中的 $k$。

第二行输入 $n$ 个正整数 $a_i(1\leq i\leq n)$。

输出格式

输出共 $T$ 行：

第 $i$ 行表示第 $i$ 组数据的结果：如果可以达到 $a$ 序列，则输出 ^_^；否则输出 QwQ。

数据范围

对于 $20\%$ 的数据，$1\leq n\leq 10$，且有 $k=2,0\leq a_i\leq 100$。

对于另外 $20\%$ 的数据，$1\leq n\leq 30$，且有 $2\leq k\leq 10,0\leq a_i\leq 2000$。

对于 $100\%$ 的数据，$1\leq n\leq 30,2\leq k\leq 100,0\leq a_i\leq 10^{16},1\leq T\leq 5 $。

3
4 100
0 0 0 0
1 2
1
3 2
0 1 3

^_^
^_^
QwQ