문제

: ^은 무엇인가요?

• 피돌이 : 이요!
• 수돌이 : 이요!

퀴즈 대회에서 이 질문에 대해 피돌이는 ^를 XOR()로 보아서 을 답했고 수돌이는 ^를 지수를 나타내는 로 보아서 이라고 답했다. 이런 혼선을 막기 위해, 퀴즈 대회의 출제자는 ^를 XOR로 볼 때와 지수로 볼 때의 답이 같도록 문제를 만들기로 했다. 하지만 두 개의 수에 대해서 문제를 만드는 것은 너무 쉽다고 생각한 퀴즈 출제자는, 다음과 같이 만들 문제를 바꿨다.

• 세 개의 수 에 대해 피돌이와 수돌이가 계산하는 ^ ^ 값이 같아야 한다.
• 피돌이는 ^기호를 항상 XOR로 본다. 즉 ^ ^ 를 로 계산한다.
• 수돌이는 ^기호를 항상 지수로 본다. 즉 ^ ^ 를 로 계산한다. 를 계산할 때는 먼저 를 계산한 후 이 값이 의 지수에 있다고 생각하여 계산한다.

, , 는 각각 을 만족하는 양의 정수일 때, 위 조건을 만족하는 세 값 로 가능한 경우의 수를 구해보자. 단, 답이 너무 커질 수 있으므로 답을 로 나눈 나머지를 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 가 주어진다.

각 테스트 케이스의 첫째 줄에 양의 정수 , , 이 공백을 두고 주어진다.

모든 테스트 케이스에서 의 합, 의 합, 의 합은 각각 을 넘지 않는다.

출력

각 테스트 케이스의 첫째 줄에 세 값 로 가능한 경우의 수를 로 나눈 나머지를 출력한다.

노트

첫 번째 테스트케이스에서, 로는 이 가능하다.

두 번째 테스트케이스에서, 로는 이 가능하다.