Football

Little Square의 학교에서 연례 축구 경기를 준비한다. 두 팀의 주장은 Little Square와 Little Triangle이다. 두 사람은 학교의 N개 반에서 팀원을 뽑는다. 팀 선발은 다음과 같이 진행된다.

• Little Square와 Little Triangle이 번갈아 가며 사람을 뽑는다. Little Square가 먼저 시작한다.
• 한 차례에는 한 반의 학생만 뽑을 수 있다.
• 한 차례에 최소 한 명, 최대 K명의 학생을 뽑을 수 있다.
• 한 차례에 뽑을 수 있는 학생 수는 바로 전 차례에 뽑은 학생 수 이하여야 한다.
• 마지막 학생을 뽑은 주장이 ”Fo(1)otball” 상을 받는다.

두 주장은 전체적으로 몇 명을 뽑는지는 신경 쓰지 않고, 축구 실력 면에서 모든 학생은 동일하다. 두 사람이 관심을 두는 것은 오직 ”Fo(1)otball” 상뿐이다. 두 사람 모두 완벽한 전략을 사용한다고 가정할 때, 상을 받는 사람은 누구인가?

각 테스트 파일에는 서로 다른 상황을 나타내는 여러 테스트 케이스가 들어 있다. 첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 각 테스트 케이스의 설명이 나온다. 테스트 케이스의 첫 줄에는 N과 K가 주어진다. 둘째 줄에는 Little Square의 학교에 있는 반들의 크기를 나타내는 N개의 양의 정수가 주어진다.

T개 테스트 케이스의 답을 공백 없이 한 줄에 출력한다. 어떤 테스트 케이스에서 Little Square가 상을 받으면 1을, 그렇지 않으면 0을 출력한다.

• T ≤ 100,000
• 테스트 파일에 있는 모든 테스트 케이스의 N 값의 합을 ΣN이라 하자. ΣN ≤ 100,000
• K, 모든 반의 크기 ≤ 1,000,000,000

첫 번째 테스트에서는 학생이 모두 5명이고, K = 1이므로 매 차례에 정확히 한 명을 뽑아야 한다. 따라서 선발은 정확히 5차례 진행되고, 마지막 학생은 Little Square의 차례에 뽑히므로 Little Square가 이긴다.

두 번째 테스트에서 Little Square는 먼저 첫 번째 반에서 두 명을 뽑을 수 있다. 그러면 이후 네 차례에는 모든 반에 학생이 한 명씩만 남아 있으므로 두 주장이 한 명씩 뽑게 되고, Little Square가 이긴다.

세 번째 테스트에서 Little Square가 먼저 한 명을 뽑는 것이 이기는 전략 중 하나이다.