P10246 Exciting Days

There is a saying on the Internet that October $24$ is “Programmers’ Day”, because $1024$ is exactly $2^{10}$, and computers are closely related to binary. If an alien civilization does not use the Earth calendar, and may not even use traditional binary computers, would they have a similar tradition?

On a certain planet, the calendar is numerically different from Earth’s, but its structure is generally similar. Specifically, a year has $n$ months, and month $i$ has $a_i$ days. Define the **characteristic value** of date month $m$ day $d$ as follows: write $m$ and $d$ in decimal (with no leading $0$), and then concatenate them directly. For example, the characteristic value of March $7$ is $37$, and the characteristic value of December $20$ is $1220$. If the characteristic value of a date is a natural-number power of $k$, then this date is called a **generalized Programmers’ Day**. Can you find all generalized Programmers’ Days on this planet?

**This problem has multiple test cases.** The first line of the input contains a positive integer $T$, the number of test cases. Each test case consists of two lines. The first line contains two positive integers $n, k$, with the same meanings as in the statement. The second line contains $n$ positive integers $a_1,\ldots,a_n$, representing the number of days in each month.

For each test case, first output one line containing a non-negative integer, the number of generalized Programmers’ Days. Then output several lines, each containing a pair of positive integers $m, d$ separated by a space, meaning that month $m$ day $d$ is a Programmers’ Day. Within the same test case, the dates should be printed in the order they occur in the year.

[Sample Explanation]. For the first test case, the aliens’ calendar has two months: the first month has $11$ days, and the second month has $12$ days. We need the characteristic value to be an integer power of $1$, which can only be $1$. However, the characteristic value of any date **has at least two digits**, so there is no valid date. For the second test case, this is the Gregorian calendar of humans in a leap year. It is easy to see that the characteristic values of the printed dates are indeed natural-number powers of $2$. [Constraints]. This problem has $25$ test points, each worth $4$ points. In the constraints, $\sum n$ denotes the sum of $n$ over all test cases. For example, in the sample, $\sum n=14$. |Test Point ID|$T\le$|$\sum n\le$|$a_i\le$|Special Property| |:-:|:-:|:-:|:-:|:-:| |$1$|$1$|$1000$|$1000$|$k=6$| |$2\sim 3$|$1$|$1000$|$1000$|| |$4\sim 6$|$3$|$1000$|$1000$|| |$7\sim 11$|$3$|$10^4$|$10^4$|| |$12\sim 14$|$1$|$3\times 10^5$|$10^9$|| |$15\sim 17$|$3$|$3\times 10^5$|$10^9$|| |$18\sim 19$|$10^4$|$10^4$|$10^9$|$n=1$| |$20\sim 21$|$10^4$|$9\times 10^4$|$10^9$|$n\le 9$| |$22\sim 25$|$10^4$|$3\times 10^5$|$10^9$|| For all testdata, it is guaranteed that $1\le T\le 10^4$, $1\le n\le 3\times 10^5$, $1\le \sum n\le 3\times 10^5$, $1\le a_i,k\le 10^9$, and all inputs are integers. To avoid excessive constant-factor optimizations, it is guaranteed that, for a single test point, the number of printed dates does not exceed $2\times 10^4$. Translated by ChatGPT 5