33813번 - 홀수 학번은 홀수 문제만 서브태스크

문제

김명식 선생님은 매주 학생들에게 1ドル$번부터 $N$번까지 번호가 붙여진 수학 문제 $N$문항을 숙제로 내주십니다. 하지만 모든 문제를 풀기에는 양이 너무 많아서 홀수 학번은 문항 번호가 홀수인 문제만, 짝수 학번은 문항 번호가 짝수인 문제만 풀도록 지도하십니다.

그런데 홀수 학번인 도윤이는 문항 수가 홀수일 때마다 짝수 학번보다 더 많은 문제를 풀고 있다는 사실을 깨달았습니다. 이에 불만을 품은 도윤이가 문제를 제기하자, 선생님은 새로운 방법을 제안하셨습니다.

홀수 학번 학생은 문항 번호에 김명식 선생님이 가장 좋아하는 수 $K$를 곱한 뒤, 이를 이진수로 변환했을 때 1ドル$의 개수가 홀수인 문제만 풀이합니다. 짝수 학번 학생은 문항 번호에 김명식 선생님이 가장 좋아하는 수 $K$를 곱한 뒤, 이를 이진수로 변환했을 때 1ドル$의 개수가 짝수인 문제만 풀이합니다. 이를테면, $K=3$일 때, 6ドル$번 문항은 6ドル \times 3=18=10010_{(2)}$이므로 짝수 학번 학생이, 7ドル$번 문항은 7ドル \times 3=21=10101_{(2)}$이므로 홀수 학번 학생이 해결해야 합니다.

김명식 선생님은 이 방법을 따라도 전체적으로 보면 두 학번이 푸는 문제의 수가 비슷해질 것이라고 말씀하셨습니다.

도윤이는 선생님의 말씀이 타당한지 직접 계산하려고 합니다. $N$이 주어지면, 홀수 학번이 풀어야 하는 문제의 수와 짝수 학번이 풀어야 하는 문제의 수의 차를 계산하는 프로그램을 작성하세요.

입력

첫째 줄에 김명식 선생님이 좋아하는 수 $K$와 테스트 케이스의 개수 $T$가 띄어쓰기로 구분되어 주어집니다.

다음 $T$개 줄에 걸쳐 줄마다 $N_i$가 주어집니다. 이는 $i$번째 테스트 케이스에서 학생들이 풀어야 하는 문항 수가 $N_i$임을 의미합니다.

출력

각각의 테스트 케이스마다 $($홀수 학번이 풀어야 하는 문제의 수$) - ($짝수 학번이 풀어야 하는 문제의 수$)$의 값을 계산하여, 줄 바꿈으로 구분하여 출력하세요.

제한

• 1ドル \le T \le 1000$
• 1ドル \le K \le 10000$
• 1ドル \le N_i \le 10^{10}$ $(1 \le i \le T)$

서브태스크

힌트