In a cozy village, there lived a wise wizard named Aysu. One day, Aysu accidentally cast a powerful spell that twisted reality in strange ways, causing chaos in the town. But Burak, a clever mathematician, discovered a solution hidden in numbers that could break Aysu's spell. However, it needed someone brave enough to face the danger. That's when Halil, known for his courage, volunteered for the task.

Together, guided by Burak's wisdom and Halil's bravery, they set out on a risky journey to challenge Aysu's magic. Their journey was quite dangerous because one mistake could lead to the destruction of the entire village.

The task was simple: They need to determine if \(c\) could be formed by adding, subtracting, or multiplying \(a\) and \(b\). With the power of numbers and their determination, they aimed to save their village from the enchantment's grip.

This task was quite simple for Burak, but he is unable to do it due to damage he received during the trip. Halil asks you to help him. Can you help him? The welfare and peace of the beloved village are in your hands.

Input

• The first line contains a single integer \(n\), the number of triplets in the test case.
• Each of the next \(n\) lines contains three integers \(a\), \(b\), and \(c\), the elements of the triplet.
• \(1 \leq n \leq 2^{12}\)
• \(1 \leq a, b \lt 2^{16}\)
• \(1 \leq c \lt 2^{32}\)

Output

Print \(\mathbf{1}\) if the \(c\) can be acquired by addition, subtraction, or multiplication; otherwise, print \(\mathbf{0}\).

Example

Input 1:

4
2 3 5
6 9 3
4 5 20
5 3 14

Output 1:

1
1
1
0

Explanation

• First line, we can use summation: \(2 + 3 = 5\)
• Second line, we can use substraction: \(9 - 6 = 3\)
• Third line, we can use multiplication: \(4 \times 5 = 20\)
• Fourth line, we cannot acquire \(14\) from \(5\) and \(3\).