어느 날 Koreatech 전파탐지 공학 팀이 우주로부터 알 수 없는 신호를 포착하였습니다.
그때 옆 병천 나라 순대 연구소에서 일하고 있던 종욱이와 김상진 교수님 연구실에서 일하고 있던 재우가 한 가지 사실을 알아냅니다.
바로 영준이가 알아낸 우주에서 날아온 시그널이 종욱이가 개발한 델타파와 재우가 개발한 알파파의 일부의 bit를 반전하여 bit-or 연산을 하면 같은 신호를 만들어 낼 수 있다는 사실을 말입니다.
자, 이제 어떤 신호들이 발견되었는지 한번 확인해 볼까요?
첫 줄에는 테스트 케이스 T(1 ≤ T ≤ 3 × 104)가 주어집니다.
그다음 줄부터 아래의 입력 정보들이 반복하여 주어집니다.
3개의 정수 A(1 ≤ A ≤ 109), B(1 ≤ B ≤ 109), C(1 ≤ C ≤ 109)가 주어집니다. A는 델타파, B는 알파파, C는 우주에서 날아온 신호를 나타냅니다.
각 줄에는 정수 A와 정수 B의 bit를 반전시켜 bit or 연산을 하여 C를 만들 수 있는 최소한의 반전 횟수를 출력합니다.
3
1 2 0
7 3 5
9 9 6
2
2
6