問題文


線形合同法はひと昔前の乱数生成によく使われていた方法です。 周期が長くないため、現在ではあまり使われていません。

線形合同法ではパラメータ を決め、乱数列 を次のように定義します。


この問題においては、 とします。

個のテストケースに対して、以下の問題の答えを出力してください。

  • が与えられたとき、乱数列の 番目の値 を答えてください。

制約


  • 入力は全て整数である

入力


出力


行出力してください。 について、 行目には 番目のテストケースの答えを出力してください。

入出力例


入力例
5
2 1 1 5
1 3 3 3
15311432 0 1 8388608
3 1 1 1000000000
123 456 789 10
出力例
63
12
1
351549422
639657991

Submit


Go (1.14)