Sixes and Sevens

Sixes and Sevens is a fun game played by children to improve their arithmetic skills. The children sit in a circle to play the game. The first child is given a special box to start the game. The box has a single button and a small display screen. Pressing the button either displays the number 1 (if the display is currently blank) or displays the number which is one larger than the number currently in the display. On seeing the number, the child must pass the box to the child on either the left or the right, depending on the number displayed. Some numbers are special numbers. These either have at least one 6 among their digits or they are divisible by 7, or possibly both of these. The first child begins by passing the box to the child on the right. The direction of passing is maintained until a special number is displayed. Each time this happens the direction of passing is reversed. When a child receives the box they press the button (which displays the next integer in sequence). They then determine whether or not they have a special number and then pass the box to the adjacent child in the correct direction.

There are two minor modifications to the game. The division by 7 can be a bit tricky so the box has a special sensor to determine the direction in which it is being passed. If the child begins to pass the box in the wrong direction, a warning beep sounds to alert the child to this. The warning beep ensures that the box is always passed in the correct direction. The second modification is that the teacher has entered a target number into the box. When the child with the box presses the button and the number revealed is the secret target number, the box plays a merry tune and releases a small reward (usually some kind of sweet) for the child.

A small example should help to clarify the process. Suppose that we have 12 children. For convenience we will number them from 1 to 12. Child 2 sits to the right of child 1; child 3 sits to the right of child 2 and so on until we reach child 12. However, the children are sitting in a circle so child 1 is sitting to the right of child 12. Child 1 is given the box at the start of the game. Child 1 presses the button, producing the number 1 (which is not a special number) and then passes the box to child 2 (on the right). Child 2 presses the button, revealing the number 2 and also passes the box to the right. The teacher has entered 30 as the secret target number. The first 30 button presses are shown in the sequence below. Each pair of values begins with the number displayed on the box. This is followed by the number of the child holding the box (having just pressed the button).

(1 1), (2 2), (3 3), (4 4), (5 5), (6 6), (7 5), (8 6), (9 7), (10 8),
(11 9), (12 10), (13 11), (14 12), (15 11), (16 10), (17 11), (18 12), (19 1), (20 2),
(21 3), (22 2), (23 1), (24 12), (25 11), (26 10), (27 11), (28 12), (29 11), (30 10)

Children 1 to 5 all pass the box to the child on the right. Child 6 then presses the button, revealing the special number 6, so the direction is reversed and the box is passed to the left, to child 5. Child 5 now presses the button, revealing another special number 7. The direction changes again so the box is passed to the right to child 6. The next direction change occurs with the number 14. Child 12 passes the box to the left. 16 is the next special number so child 10 passes the box to the right. Notice that when the box is displaying 18 it is still being passed to the right but the child to the right of child 12 is child 1. At 21 the direction changes again so child 3 passes the box to the left. At 26 the direction switches to the right. At 28 we have the final direction change, to the left. In this example the number 30 is the secret target number so child 10 is the one who gets the reward.

In the example above, we have direction changes for each of the numbers 6, 16 and 26. Each of these contains the digit 6 (at least once). We also have direction changes for each of the numbers 7, 14, 21 and 28. These are all multiples of 7. If the game had continued we would have seen direction changes at numbers like 56 and 63 These are multiples of 7 and contain the digit 6.

In this problem you will be given several games to analyse. These will be significantly larger than the small example above. In particular there will be 1000 children (numbered 1 to 1000). Again they are sitting (in number order) in a circle, with child 2 to the right of child 1 and child 1 to the right of child 1000. For each game, you will be given the secret target number and must find the number of the child who will get the reward at the end of the game. The secret target numbers can be up to 80 digits in length. These are provided as a string of digits and can be processed as a string. There is no need for these long numbers to be processed in numeric form.

Input/Output description: The first line of the input data will contain two integers C and N, separated by a space. C is the number of children and N is the number of games. N lines follow. Each of these contains a string of digits. This is the integer value of the secret target number. Your answer is the number of the child who receives the reward at the end of the game. Combine all answers into a single string, separated by single spaces.

Example 1:

input:
12 2
30
100

answer:
10 2

Example 2:

input:
1000 8
27
993
5493
97708
220840
3875804
50212234
660247233

answer:
11 47 107 876 766 752 938 715