골프 고퍼

작년에 성가신 고퍼 무리가 과수원에 자리를 잡았다. 우리는 미니 골프장을 열어 일하는 분야를 바꿔 보려 했지만, 고퍼들이 이곳까지 따라온 것으로 보인다. 이번에도 고퍼가 몇 마리인지 알아내야 한다. 고퍼는 숨어 지내며 밤에만 활동하므로 직접 관찰할 수 없고, 우리는 밤에 자고 싶다. 우리가 아는 것은 고퍼의 수가 1 이상 $M$ 이하라는 것뿐이다.

우리 미니 골프장은 18개 홀마다 작은 전동 풍차가 하나씩 있는 것으로 유명하다. $i$번째 풍차의 날개는 $B_i$개이며, $2 \le B_i \le 18$을 만족한다. 날개는 시계 방향으로 0부터 $B_i-1$까지 번호가 붙어 있다. 매일 밤 자러 가기 전에 풍차를 모두 끄고, 각 풍차의 0번 날개가 아래를 향하도록 맞춰 둔다. 이는 다음 날 풍차가 제대로 충전되도록 하기 위해 중요하다. 그런데 아침에 일어나 보면 풍차가 흐트러져 있을 때가 있다. 이 골프장은 바람이 없는 곳에 있으므로, 짓궂은 고퍼의 짓이 틀림없다.

매일 밤 고퍼들이 한 마리씩 차례로 나온다. 각 고퍼는 풍차 하나를 독립적으로, 같은 확률로 골라 반시계 방향으로 날개 한 칸만큼 돌린다. 예를 들어 날개가 3개이고 0번이 아래를 향한 풍차라면, 처음 건드린 고퍼는 1번이 아래를 향하도록 돌린다. 이후 같은 풍차를 건드린 고퍼들이 돌리면 아래를 향한 날개 번호는 2, 0, 1 순서로 바뀐다.

우리는 계획을 세웠다. 난이도를 조절할 수 있도록 풍차의 날개 수를 쉽게 바꿀 수 있게 설계했고, 이를 활용하려 한다. 매일 밤 자기 전에 주어진 범위 안에서 18개 풍차 각각의 날개 수를 고를 수 있다. 풍차마다 날개 수가 같을 필요는 없고, 밤마다 같은 선택을 할 필요도 없다. 아침에는 각 풍차에서 아래를 향한 날개의 번호를 확인한다. 고퍼의 수 $G$를 알아내는 데 $N$일 밤이 있다. 도와줄 수 있겠는가?

$1 \le T \le 20$.