ストーリー

チェリーちゃんを含めた $M$ 人は $N$ 日間花を咲かせる努力をしました. その結果, $k~(1 \leq k \leq N)$ 日目には $k$ 輪の花を咲かせることができました.

つまり, $N$ 日間で合計 $\displaystyle \sum_{k=1}^N k$ 輪の花を咲かせました.

問題文

$\displaystyle \sum_{k=1}^N k$ を $M$ で割った余りを求めよ.

$T$ 個のテストケースについて答えよ.

制約

• $1 \leq T \leq 2 \times 10^5$
• 各テストケースに対する制約
• $1 \leq N \lt 10^{4 \times 10^6}$.
• $1 \leq M \leq 10^9$
• テストファイルに関する制約
• $T$ 個のテストケースにおける $N$ の桁数の総和は $4 \times 10^6$ 以下である.

入力

$T$
${\rm Testcase}_1$
${\rm Testcase}_2$
$\vdots$
${\rm Testcase}_T$

$N$ $M$

出力

出力は $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には, 第 $t$ テストケースに対する解答を整数で出力せよ.

最後に改行を忘れないこと.

サンプル

3
3 100
5 10
123456789012345678901234567890 20240223

6
5
1774557