BFS Practice 1

Problem Description

You are given a number $a$. Each step you may choose one of the following four operations:

1. Add one to $a$.
2. Multiply $a$ by $2$.
3. Multiply $a$ by $3$.
4. Subtract one from $a$.

Find the minimum number of steps to change $a$ into $b$.

You need to answer $q$ queries, with targets $b_1, b_2, \dots, b_q$; output the minimum number of steps to change $a$ into $b_1, b_2, \dots, b_q$.

Input Format

The first line contains two integers $a, q$.

The next line contains $q$ integers $b_1, \dots, b_q$.

Output Format

Output $q$ numbers, the minimum number of steps to change $a$ into $b_1, b_2, \dots, b_q$ respectively.

Sample Input

3 10
1 2 3 4 5 6 7 8 9 10

Sample Output

2 1 0 1 2 1 2 2 1 2

Constraints

For all data, $1\le a, q, b_i \le 10^5$.