피보나치 음악

작곡가 철수는 피보나치 수열로 만든 피아노 곡을 우연히 유튜브에서 보게 되었다. 피보나치 수열은 $f_1 = 1$, $f_2 = 1$, $f_{n+2} = f_{n+1} + f_n$ (모든 $n \ge 1$)을 만족하는 수열이다.

이 곡은 피보나치 수열의 각 자리 숫자에 해당하는 건반을 눌러서 만들었다. 피보나치 수열의 첫 8개 항으로 곡을 만든다면, 다음과 같이 건반을 총 10번 누르게 된다.

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

철수는 자신도 이 방법을 써 보기로 마음먹었다. 그런데 피보나치 수열은 너무 빠르게 증가해서, 덧셈에 약한 철수가 계산하기에는 어려웠다.

그래서 철수는 방법을 조금 바꾸기로 했다. 철수는 어떤 수 $M$을 정한 후, 피보나치 수열의 각 항을 $M$으로 나눈 나머지를 구하고, 각 수의 각 자리 숫자로 새로운 수열을 만들어 이에 따라 피아노 곡을 쓰려고 한다.

예를 들어 $M=10$일 때, 새로운 수열은 다음과 같다.

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

따라서 철수는 1 → 1 → 2 → 3 → 5 → 8 → 3 → 1 → 4 → … 순으로 건반을 누르게 된다.

이때, 철수는 어떤 $N$에 대해 $N$번째로 누르게 되는 건반의 번호(새로운 수열의 $N$번째 항)가 궁금해졌다.

$Q$개의 $N$이 질의로 주어졌을 때, 각각의 질의에 대해 $N$번째로 누르게 되는 건반의 번호를 출력하는 프로그램을 작성하여라.

첫 번째 줄에는 정수 $Q$와 $M$이 공백을 사이에 두고 주어진다.

두 번째 줄부터 $Q$개의 줄에 각각의 질의를 나타내는 정수 $N$이 주어진다.

각각의 $N$에 대해, $N$번째로 누르게 되는 건반의 번호(새로운 수열의 $N$번째 항)를 입력에 주어진 순서대로 총 $Q$개의 줄에 출력한다.

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