시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 363 | 109 | 87 | 43.500% |
n명을 m개의 그룹으로 나누는 방법의 수를 제 2종 스털링 수(Stirling numbers of the second kind)라고 하고, S(n,m)으로 표현한다. S(n,k)는 크기가 n인 집합을 k개의 공집합이 아닌 부분집합으로 나누는 방법의 수와 같다. 예를 들어, n=4, k=2일 때 다음과 같이 나눌 수 있다.
S(n,m)은 다음과 같이 계산할 수 있다.
1 ≤ m ≤ n을 만족하는 n과 m이 주어졌을 때, S(n,m)가 짝수이면 0, 홀수이면 1을 출력하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 D가 주어진다. (1 ≤ D ≤ 200) 각 테스트 케이스는 한 줄로 이루어져 있고, n과 m이 공백으로 구분되져 있다. (1 ≤ m ≤ n ≤ 109)
각 테스트 케이스에 대해서, S(n,m)이 짝수이면 0, 홀수이면 1을 출력한다.
1 4 2
1