問題文

あなたはプロのピアニストであり，今月は茨城県の各地で行われる運動会でピアノを弾くことになりました．茨城県のピアノは高橋流による特殊なものであり，以下の特徴を持ちます．

• 88 の鍵盤が横一列にあり，全ての鍵盤に正の整数が 1 つずつ刻まれています．左から 1, 2 番目以外の鍵盤について，刻まれた整数は 1 つ左の鍵盤と 2 つ左の鍵盤のものの和に等しいです．
  • たとえば，左から 1, 2 番目に 3, 2 とあった場合， 3 番目以降は 5, 7, 12, 19, ... と続きます．
• 1 つ以上の鍵盤の組合せを「和音」と呼びます．特に，隣り合う 2 鍵を含んでいないようなものを「美しい和音」と呼びます．
  • たとえば，「左から 1, 3, 6, 88 番目」や「左から 5 番目」は美しい和音ですが，「左から 5, 7, 8 番目」は美しい和音ではありません．
• 和音の「高橋値」は，和音を構成する鍵盤に刻まれた整数の総和で表されます．
  • たとえば，左から i 鍵目に刻まれた整数を A_i とおくと，「左から 86, 9, 1, 20 番目」から成る和音の高橋値は A_{86} + A_9 + A_1 + A_{20} に等しいです．

運動会は全部で Q 回行われます． i 回目の運動会において，開催校は創立 X_i 周年であることから，あなたは高橋値が X_i であるような美しい和音を曲に織り交ぜることにしました． i 回目の運動会で弾くピアノの左から 1, 2 番目の鍵盤にはそれぞれ a_i, b_i が刻まれているとわかっているので，各 i に対し，与えられたピアノで高橋値 X_i となる美しい和音が何通りあるか答えてください．

入力

1 行目には，質問の回数 Q が与えられます．

2 行目から Q 行にわたって，i 回目の運動会に関する情報 a_i, b_i, X_i が空白区切りで与えられます．

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

出力

全部で Q 行出力してください． i 行目には， i 番目の質問に対する解答を出力してください．

入力例 1

2
1 1 1
1 1 9

出力例 1

2
2

入力例 2

3
1 2 32
5 2 1
2 1 70

出力例 2

1
0
2