금화 게임

• 한무더기만으로 이루어져 있으므로 그런디수를 정확히 계산할 필요까지는 없다.
• K가 홀수인 경우, 1,K, K^2, …은 모두 홀수이다. 따라서 어떤 액션을 취하든, 남은 금화의 홀짝이 바뀌게 된다. 처음에 금화가 짝수개였다면, 선공이 액션을 취하고 나면 홀수개가 남게되고, 후공이 액션을 취하고 나면 짝수개가 남게 된다. 즉, 0개를 남겨야 이기는 이 게임에서 선공은 절대 이길수 없다. 정리하면 처음 금화가 홀수개면 선공아 승리할 방법이 없고, 짝수개면 선공이 항상 승리한다. 1개만 가져가면 된다.
• K가 짝수인 경우는 조금 더 복잡하다. 이경우는 그냥 손으로 계산해보고, 거기에서 패턴을 찾아야 한다.. 자기 차례에 금화의 수가 (K+1)의 배수이면 이길수 없다. N%(K+1)이 K라면 K개를 가져가서 남은 갯수를 (K+1)m 으로 만들면 이길수 있다. N%(K+1)이 K의 배수가 아니라면.. N%(K+1)의 홀짝성에 따라 달라진다. 저 값이 홀수라면 1개만 가져가는 것으로 이길수 있다. 저 값이 짝수라면 이길 방법이 없다.
• 위에 적은 것을 정리하면 결국 어떤 n에 대해서든 승리방법을 O(1)에 계산 가능하다.

"""Solution code for "BOJ 5386. 금화 게임".

- Problem link: https://www.acmicpc.net/problem/5386
- Solution link: http://www.teferi.net/ps/problems/boj/5386

Tags: [Ad hoc]
"""


def main():
    T = int(input())
    for _ in range(T):
        S, K = [int(x) for x in input().split()]
        if K % 2 == 1:
            print(S % 2)
        else:
            t = S % (K + 1)
            print(K if t == K else t % 2)


if __name__ == '__main__':
    main()