Background

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?

Problem Description

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?

Input Format

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.

Output Format

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.

2
2 1
11 12
12 2
31 29 31 30 31 30 31 31 30 31 30 31

0
7
1 6
1 28
3 2
5 12
6 4
10 24
12 8

Hint

[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$.

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