Leo didn't do all the job in his last problem, somebody gave him the numbers in a convenient base. It was the bottleneck of the problem... Now your task is to do this job.

Input

The first line of input contains three integers T, the number of test cases, B1, the first base, B2, the second base.
Follow 2×T lines.
For each test case, on the first line your are given one integer k.
On the second line you are given k integers : the digits of N in base B1.

N = a₀×B1⁰ + ... + a_i×B1ⁱ + ... + a_k-1×B1^k-1

Output

For each test case, you have to print the number N in base B2. See sample for details.

Example

Input:
1 10 100
5
5 4 3 2 1

Output:
3
45 23 1

Explanations

For the lonely case, N = 5×10⁰ + 4×10¹ + 3×10² + 2×10³ + 1×10⁴ = 12345.
We have: N = 45×100⁰ + 23×100¹ + 1×100². You have to print 3, the number of digits, then the digits: 45, 23 and 1.

Constraints

0 < T <= 50
1 < B1,B2 <= 10^9
1 < k <= 10000
0 <= ai < B1  , ak-1>0

Time limit is sqrt(T_basic_pike_code * T_awaited_python_code) = sqrt(13.34*6.97), based on my Python3/Pike experiments.
You may try before the tutorial edition.
Have fun ;-)

Edit(2017-02-11) : With compiler updates, a new time limit is set.
Time limit is sqrt(T_basic_pike_code * T_awaited_python_code) = sqrt(3.93*1.57), based on my Python3/Pike experiments.
Thanks @Blue_Mary for pointing this out.

---

hide comments

< Previous 1 2 Next >
	[Rampage] Blue.Mary: 2016-06-09 08:37:11 Pike is a C-like language; I think the key to this problem is the right algorithm, not the language choice. =(Francky)=> Yes, sure. But the same algorithm, almost exact copy, will give PIKE_awaited faster than PYTHON_awaited. At time of publication, C/C++ would have been much difficult to implement ; it may be not true today if gmp is available. For the basic algorithm, PIKE was the fastest so it needs to gives TLE. I set time limit between the fastest-lang_easiest_basic_code, and slowest-lang_awaited. I hope this method allows all good algorithm to get AC in any language, and TLE with basic method even with fast language. Sorry if I was a bit unclear. Regards. Last edit: 2016-06-09 09:10:14
	Francky: 2014-03-19 23:48:11 I've reduce a bit time limit, to be between T_pike_basic and T_python3_awaited. Edit : I've allowed all languages ; based on my experiments, it will be hard to get AC with C-like. Last edit: 2014-03-19 23:49:56