Fibonacci Music

Cheolsu, a composer, happened to see a piano piece built from the Fibonacci sequence on YouTube. The Fibonacci sequence satisfies $f_1 = 1$, $f_2 = 1$, and $f_{n+2} = f_{n+1} + f_n$ for all $n \ge 1$.

The piece was made by pressing the key corresponding to each digit of the Fibonacci sequence. If the piece uses the first 8 terms of the Fibonacci sequence, the keys are pressed 10 times in total, as follows.

1 → 1 → 2 → 3 → 5 → 8 → 1 → 3 → 2 → 1

Cheolsu decided to try this method himself. But the Fibonacci sequence grows so fast that it was hard for him to compute, since he is weak at addition.

So he changed the method a little. After choosing a number $M$, he takes the remainder of each term of the Fibonacci sequence divided by $M$, builds a new sequence from the individual digits of each number, and writes a piano piece from it.

For example, when $M=10$, the new sequence is as follows.

{1, 1, 2, 3, 5, 8, 3, 1, …}

So Cheolsu presses keys in the order 1 → 1 → 2 → 3 → 5 → 8 → 3 → 1 → 4 → …

At this point, for a given $N$, Cheolsu wondered about the number of the key pressed $N$-th (that is, the $N$-th term of the new sequence).

Given $Q$ values of $N$ as queries, write a program that outputs the number of the key pressed $N$-th for each query.

The first line gives the integers $Q$ and $M$, separated by a space.

From the second line, $Q$ lines follow, each giving the integer $N$ that represents a query.

For each $N$, output the number of the key pressed $N$-th (the $N$-th term of the new sequence) on one line, in the order the queries appear in the input, for a total of $Q$ lines.

• $1 \le N \le 10^{15}$
• $2 \le M \le 1{,}000$
• $1 \le Q \le 100{,}000$