Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Adding Powers

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSuppose you are performing the following algorithm. There is an array $$$v_1, v_2, \dots, v_n$$$ filled with zeroes at start. The following operation is applied to the array several times — at $$$i$$$-th step ($$$0$$$-indexed) you can:

- either choose position $$$pos$$$ ($$$1 \le pos \le n$$$) and increase $$$v_{pos}$$$ by $$$k^i$$$;
- or not choose any position and skip this step.

You can choose how the algorithm would behave on each step and when to stop it. The question is: can you make array $$$v$$$ equal to the given array $$$a$$$ ($$$v_j = a_j$$$ for each $$$j$$$) after some step?

Input

The first line contains one integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of test cases. Next $$$2T$$$ lines contain test cases — two lines per test case.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 30$$$, $$$2 \le k \le 100$$$) — the size of arrays $$$v$$$ and $$$a$$$ and value $$$k$$$ used in the algorithm.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{16}$$$) — the array you'd like to achieve.

Output

For each test case print YES (case insensitive) if you can achieve the array $$$a$$$ after some step or NO (case insensitive) otherwise.

Example

Input

5 4 100 0 0 0 0 1 2 1 3 4 1 4 1 3 2 0 1 3 3 9 0 59049 810

Output

YES YES NO NO YES

Note

In the first test case, you can stop the algorithm before the $$$0$$$-th step, or don't choose any position several times and stop the algorithm.

In the second test case, you can add $$$k^0$$$ to $$$v_1$$$ and stop the algorithm.

In the third test case, you can't make two $$$1$$$ in the array $$$v$$$.

In the fifth test case, you can skip $$$9^0$$$ and $$$9^1$$$, then add $$$9^2$$$ and $$$9^3$$$ to $$$v_3$$$, skip $$$9^4$$$ and finally, add $$$9^5$$$ to $$$v_2$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/04/2020 00:00:12 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|