Minimum Hours to Reach Bacteria Threshold

You are given several petri dishes, each containing an initial number of bacteria. Every hour, the total number of bacteria across all dishes is multiplied by a growth factor k. Your task is to determine the minimum number of hours required for the total number of bacteria to reach or exceed a given threshold T.

Problem Details:
For each test case, you are provided with three integers: n (the number of petri dishes), k (the growth multiplier), and T (the threshold). On the next line, you are given n integers representing the initial bacteria counts for each dish.

Formally, let S₀ be the sum of the initial bacteria counts. At each hour h the bacteria count becomes:

S_h = k × S_h-1

You need to compute the minimum h such that S_h ≥ T.

inputFormat

The input is given via stdin and has the following format:

T
n1 k1 T1
initial_counts1
...
nT kT TT
initial_countsT

Here, the first line contains an integer T indicating the number of test cases. Each test case consists of two lines. The first line of a test case contains three integers n, k, and T. The second line contains n space-separated integers representing the initial bacteria counts.

outputFormat

For each test case, output on a separate line the minimum number of hours required for the total bacteria count to reach or exceed the threshold T.

The output should be printed to stdout.

## sample

3
3 2 100
5 7 9
2 3 200
20 30
4 5 1000
100 100 100 100

3
2
1

</p>