Server Time:

User's AC Ratio in this contest

0.0% (0/13)

Submission's AC Ratio in this contest

0.0% (0/30)

Description

有一種數列叫增殖數列,顧名思義這個數列會增殖,怎麼個增殖法呢?
這個數列的第一項是 $1$ ,第二項是 $12$ ,第三項是 $123$ ,
第 $n$ 項是 $123456789101112\cdots n$ 。

現在給你一個 $n$ ,你能求出數列第 $n$ 項是多少嗎?
因為這個數字很大,所以只要輸出第 $n$ 項除以 $m$ 的餘數就好。

Input Format

第一行有一個數字 $t\ (t\leq500)$ ,代表有 $t$ 筆測試資料。
接下來 $t$ 行,每行有兩個正整數 $n, m\ (n,m\leq10^ 9)$ 分別如題目所述。

Output Format

請輸出數列第 $n$ 項除以 $m$ 的餘數。

Sample Input 1

3
1 8
2 6
6 20

Sample Output 1

1
0
16

Sample Input 2

3
123 456
426 520
672 87

Sample Output 2

99
426
33

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 $n\leq9$ 5
2 0~7 $n\leq10^ 4$ 25
3 0~13 無特別限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3
1 1000 65536 65536 1 2 3
2 1000 65536 65536 2 3
3 1000 65536 65536 2 3
4 1000 65536 65536 2 3
5 1000 65536 65536 2 3
6 1000 65536 65536 2 3
7 1000 65536 65536 2 3
8 1000 65536 65536 3
9 1000 65536 65536 3
10 1000 65536 65536 3
11 1000 65536 65536 3
12 1000 65536 65536 3
13 1000 65536 65536 3