Problem Description

You are a professional pianist, and this month you are scheduled to play the piano at sports days held across Ibaraki Prefecture. The pianos in Ibaraki are special, designed in the Takahashi style, and have the following features:

• There are 88 keys arranged in a single row, and each key is engraved with a positive integer. For keys other than the first and second from the left, the engraved integer is equal to the sum of the integers on the key one position to the left and the key two positions to the left.
• For example, if the first and second keys from the left are engraved with 3 and 2, respectively, the keys following them will be engraved with 5, 7, 12, 19, ...
• A combination of one or more keys is called a "chord". In particular, a chord that does not include two adjacent keys is called a "beautiful chord".
• For example, "keys 1, 3, 6, and 88 from the left" or "key 5 from the left" are beautiful chords, but "keys 5, 7, and 8 from the left" are not.
• The "Takahashi value" of a chord is represented by the sum of the integers engraved on the keys that make up the chord.
• For example, if the integer engraved on the i-th key from the left is denoted as \( A_i \), the Takahashi value of the chord consisting of keys 86, 9, 1, and 20 from the left is equal to \( A_{86} + A_9 + A_1 + A_{20} \).

There will be a total of \( Q \) sports days. For the i-th sports day, the hosting school is celebrating its \( X_i \)-th founding anniversary, so you have decided to incorporate a beautiful chord with a Takahashi value of \( X_i \) into your piece. You know that the first and second keys from the left on the piano for the i-th sports day are engraved with \( a_i \) and \( b_i \), respectively. For each \( i \), determine how many beautiful chords with a Takahashi value of \( X_i \) can be formed on the given piano.

Input Format

The first line contains the number of queries \( Q \).

The next \( Q \) lines contain the information for the i-th sports day \( a_i, b_i, X_i \) separated by spaces.

\( Q \) \( a_1 \) \( b_1 \) \( X_1 \) \( a_2 \) \( b_2 \) \( X_2 \) \( a_3 \) \( b_3 \) \( X_3 \) ... \( a_Q \) \( b_Q \) \( X_Q \)

Output Format

Output a total of \( Q \) lines. The i-th line should contain the answer to the i-th query.

Sample Input and Output

Sample Input #1

2
1 1 1
1 1 9

Sample Output #1

2
2

Sample Input #2

3
1 2 32
5 2 1
2 1 70

Sample Output #2

1
0
2

Notes/Hints

Constraints

• \( 1 \leq Q \leq 100000 \)
• \( 1 \leq a_i, b_i, X_i \leq 10^{17} \)
• All inputs are integers

Subtasks

Subtask 1 \[11 points\]

• \( Q \leq 100 \)
• For all \( i \), \( a_i = b_i = 1 \), \( X_i \leq 10 \)

Subtask 2 \[31 points\]

• \( Q \leq 100 \)
• \( X_i \leq 1000 \times b_i \)

Subtask 3 \[58 points\]

• No additional constraints

见题面 Input 部分

见题面 Output 部分