AT_pakencamp_2018_day3_e 美しい和音

[problemUrl]: https://atcoder.jp/contests/pakencamp-2018-day3/tasks/pakencamp_2018_day3_e あなたはプロのピアニストであり，今月は茨城県の各地で行われる運動会でピアノを弾くことになりました．茨城県のピアノは高橋流による特殊なものであり，以下の特徴を持ちます． - $ 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\ \leq\ Q\ \leq\ 100000 $ - $ 1\ \leq\ a_i,\ b_i,\ X_i\ \leq\ 10^{17} $ - 入力は全て整数 ### 小課題 小課題 $ 1 $ \[$ 11 $ 点\] - $ Q\ \leq\ 100 $ を満たす． - 全ての $ i $ に対し， $ a_i\ =\ b_i\ =\ 1 $, $ X_i\ \leq\ 10 $ を満たす． 小課題 $ 2 $ \[$ 31 $ 点\] - $ Q\ \leq\ 100 $ を満たす． - $ X_i\ \leq\ 1000\ \times\ b_i $ を満たす． 小課題 $ 3 $ \[$ 58 $ 点\] - 追加の制約はない．