Trên thế gian này có rất nhiều thứ đẹp đẽ. Những cảnh đẹp ở Ý có đẹp đẽ không? Có (vì Ý là quê của anh tôi). Những cô gái anime có đẹp đẽ không? Chắc chắn có (vì waifu của tôi nằm trong đó). Loli có đẹp không? Có chứ! Nhưng bạn biết thứ gì cũng đẹp đẽ không kém không? Những hoán vị đẹp đẽ.

Loli muốn đếm số lượng hoán vị đẹp đẽ. Hoán vị là một dãy số chứa ~n~ số nguyên khác nhau, có giá trị từ ~1~ tới ~n~ và được sắp xếp với thứ tự bất kỳ (~[1,3,2,5,4]~ là hoán vị, nhưng ~[1,2,2]~ hay ~[1,4,3]~ thì không).

Vậy hoán vị đẹp đẽ thì khác gì hoán vị thường? Có chứ! Hoán vị ~p~ có độ dài ~n~ ~(p_1, p_2, ..., p_n)~ được coi là đẹp đẽ khi thỏa mãn tính chất sau:

~\gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1~

trong đó ~gcd~ là viết tắt của Ước chung lớn nhất.

Input

• Dòng đầu chứa một số nguyên ~t~ (~1 \le t \le 100~) là số lượng testcase.
• Mỗi testcase chứa một số nguyên ~n~ (~1 \le n \le 10^6~).

Output

• Với mỗi testcase in ra một số nguyên duy nhất là số hoán vị đẹp đẽ.
• Vì số hoán vị đẹp đẽ có thể rất lớn, hãy in ra phần dư của chúng với ~10^9+7~.

Subtask

• Subtask 1 (~15\%~ điểm): ~n \le 8~.
• Subtask 2 (~15\%~ điểm): ~n \le 20~.
• Subtask 3 (~20\%~ điểm): ~n \le 100~.
• Subtask 4 (~20\%~ điểm): ~n \le 10^3~.
• Subtask 5 (~30\%~ điểm): Không có ràng buộc gì thêm.

Sample Input

4
1
2
6
30

Sample Output

0
1
36
738721209

Giải thích

• Ở testcase đầu tiên, ta chỉ có một hoán vị là ~[1]~, hoán vị này không đẹp vì ~\gcd(1 \cdot 1) = 1~.
• Ở testcase thứ hai, ta chỉ có một hoán vị đẹp đẽ là ~[2, 1]~ vì ~\gcd(1 \cdot 2, 2 \cdot 1) = 2~.

Trong một buổi kiểm tra nhảy xa, Loli - một thầy giáo đáng iu đang kiểm tra một nhóm ~n~ bạn nữ. Loli tạm đánh số các bạn từ ~1~ to ~n~, và các bạn đều đang ở vị trí ~0~. Bạn ~i~ có khả năng nhảy xa ~a_i~ đơn vị (từ vị trí ~x~ nhảy đến vị trí ~x+a_i~). Mỗi một đợt nhảy, bạn ~i~ nhảy xa ~a_i~ đơn vị về phía trước.

Ban đầu, Loli đặt chỉ một chướng ngại vật tại một vị trí bất kỳ, mục đích để kiểm tra kỹ năng nhảy vượt rào của những bạn nhảy chính xác đến vị trí đặt chướng ngại vật.

Tuy nhiên, Loli quá lười nên chỉ có thể đặt chướng ngại vật ở ~n~ vị trí đầu tiên (vị trí thứ ~1~ tới vị trí thứ ~n~). Loli không đặt chướng ngại vật ở vị trí ~0~ vì nó vô nghĩa.

Bạn có thể tìm ra số lượng bạn nữ tối đa mà Loli có thể kiểm tra kỹ năng nhảy vượt rào khi tuân theo quy tắc trên không?

Input

• Dòng đầu chứa một số nguyên ~t\ (1\le t\le 100)~ là số lượng testcase.
• Dòng đầu của mỗi testcase chứa một số nguyên ~n~ ~(1 \leq n \leq 2 \cdot 10^5)~ là số lượng các bạn nữ, cũng như là vị trí xa nhất mà Loli có thể đặt chướng ngại vật.
• Dòng thứ hai của mỗi testcase chứa ~n~ số nguyên dương ~a_1, \ldots, a_n~ ~(1 \leq a_i \leq 10^9)~, với ~a_i~ là khả năng nhảy xa của bạn nữ thứ ~i~.
• Đầu vào đảm bảo tổng các ~n~ trong ~t~ testcase không vượt quá ~2 \cdot 10^5~.

Output

• Với mỗi testcase in ra một số nguyên duy nhất là số lượng bạn nữ tối đa mà Loli có thể kiểm tra kỹ năng nhảy vượt rào.

Subtask

• Subtask 1 (~20\%~ điểm): ~n \le 20~.
• Subtask 2 (~30\%~ điểm): ~n \le 10^3~.
• Subtask 3 (~50\%~ điểm): Không có ràng buộc gì thêm.

Sample Input

3
5
1 2 3 4 5
3
1 1 1
1
8

Sample Output

3
3
0

Giải thích

Trong test đầu tiên, các bạn nữ sẽ nhảy như sau:

Nếu Loli đặt chướng ngại vật ở vị trí ~4~, thì Loli sẽ kiểm tra được ~3~ bạn: bạn ~1, 2, 4~. Dễ dàng nhận thấy Loli không thể kiểm tra hơn ~3~ bạn.

Trong test thứ hai, Loli chỉ cần đặt ở vị trí ~1~ là có thể kiểm tra được cả ~3~ bạn.

Trong test thứ ba, Loli chỉ có thể đặt ở vị trí ~1~, vì vậy không thể kiểm tra bạn nữ duy nhất được.

Loli là một lập trình viên về game. Công ty của Loli đang làm một con game AAA rất căng, họ tự tin con game cưng này sẽ đạt được Game Of The Year 2050, là một gương mặt sừng sỏ thay đổi ngành công nghiệp giải trí.

Loli được giao code một phân đoạn của game. Bối cảnh phân đoạn trong trò chơi là một nửa quả đồi, được chia thành ~n~ cột. Độ cao của cột ~i~ là ~h_i~ ~(0 \le h_1 \le h_2 \le \dots \le h_n \le 10^9)~. Người chơi sẽ thực hiện ~m~ hành động theo trình tự, mỗi hành động được đặc trưng bởi hai số ~(i, L)~, có nghĩa là nhân vật hiện tại ở cột ~i~ bắn một tia độ dài ~L~ về bên phải. Khi nhân vật ở cột ~i~ bắn một tia độ dài ~L~ về bên phải, các cột ~i + 1, i + 2, \dots, i + L~ sẽ bị giảm độ cao về bằng với độ cao hiện tại của cột ~i~.

Điểm của mỗi hành động là số lượng đất bị phá, tức là tổng mức giảm độ cao của các cột bị giảm. Công ty muốn Loli tính điểm được cộng thêm sau khi người chơi thực hiện xong mỗi một hành động.

Input

• Dòng đầu chứa một số nguyên ~n~ ~(1\le n \le 10^5)~.
• Dòng tiếp theo chứa dãy ~h_1, h_2, \dots, h_n~ là độ cao từng cột của đồi ~(0 \le h_1 \le h_2 \le \dots \le h_n \le 10^9)~.
• Dòng tiếp theo chứa số lượt chơi ~m~ ~(1\le m \le 10^5)~.
• ~m~ dòng tiếp theo mỗi dòng chứa một hành động, có dạng: ~i\ L~ ~(1 ≤ L ≤ n - i)~.

Output

• In ra trên ~m~ dòng là điểm được cộng thêm của ~m~ hành động.

Subtask

• Subtask 1 (~40\%~ điểm): ~n, m \le 5000~.
• Subtask 2 (~60\%~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

5
1 2 3 4 5
4
3 1
1 2
3 2
1 4

Sample Output 1

1
3
6
0

Giải thích

• Dãy đang có độ cao lần lượt là ~[1,2,3,4,5]~.
• Sau hành động đầu tiên, ta có độ cao của cột ~4~ được san bằng với cột ~3~, dãy mới là ~[1,2,3,3,5]~, chênh lệch tổng 1 đơn vị.
• Sau hành động thứ hai, ta có độ cao của cột ~2,3~ được san bằng với cột ~1~, dãy mới là ~[1,1,1,3,5]~, chênh lệch tổng 3 đơn vị.
• Sau hành động thứ ba, ta có độ cao của cột ~4,5~ được san bằng với cột ~3~, dãy mới là ~[1,1,1,1,1]~, chênh lệch tổng 6 đơn vị.
• Sau hành động thứ tư, ta có độ cao của cột ~2,3,4,5~ được san bằng với cột ~1~, dãy mới là ~[1,1,1,1,1]~, không đổi.

Để chuẩn bị cho sự kiện sắp tới của trường, mỗi lớp sẽ phải chuẩn bị một tiết mục đóng kịch. Được bạn bè trong lớp tin tưởng giao phó nhiệm vụ, Loli may mắn có cơ hội vào vai trong một câu chuyện cổ tích nổi tiếng. Chiều hôm đó Loli sẽ trở thành một cô Tấm hiền lành thùy mị nết na.

Truyện Tấm Cám thì ai cũng biết rồi, câu chuyện này phản ánh những mâu thuẫn trong gia đình, đặc biệt là mối quan hệ mẹ kế - con chồng; cuộc đấu tranh giữa và cái thiện thắng cái ác của người Việt.

Nhưng trước khi diễn ra cái cuộc "đấu tranh" giữa cái thiện và cái ác, thì Loli phải làm xong một công việc khó khăn thì mới được dì ghẻ cho đi chơi lễ hội huhuhu.

Dì ghẻ cho Loli một xâu kí tự gồm ~n~ chữ số, Loli phải chia dãy thành ~k~ đoạn liên tiếp sao cho giá trị của số tạo thành ở mỗi đoạn đều chia hết cho ~p~. Các đoạn có thể có độ dài tùy ý, và có thể bắt đầu bằng một hay nhiều chũ số ~0~.

Dì ghẻ bắt Loli đếm số cách thực hiện việc phân tách này. Vì dì ghẻ có test sẵn nên có thể biết được Loli trả lời đúng hay sai. Cũng vì Loli không được động vào dàn máy gaming của Cám ở nhà nên đành nhờ bạn code giúp.

Input

• Dòng đầu tiên chứa ba số nguyên ~n~, ~k~ và ~p~ ~(1 \le n \le 50000, 1 \le k \le 200, 1 \le p \le 30)~.
• Dòng thứ hai chứa dãy gồm ~n~ chữ số, từ ~0~ đến ~9~.

Output

• Gồm một số nguyên duy nhất là số cách chia dãy ~n~ chữ số thành ~k~ đoạn sao cho giá trị của mỗi đoạn đều chia hết cho ~p~.
• Do kết quả có thể rất lớn, cần in ra kết quả theo modulo ~10^9+7~.

Subtask

• Subtask 1 (~15\%~ điểm): ~p = 1~
• Subtask 2 (~15\%~ điểm): ~p = 2~
• Subtask 3 (~15\%~ điểm): ~p = 3~
• Subtask 4 (~15\%~ điểm): ~n \le 50~ và ~k \le 5~
• Subtask 5 (~15\%~ điểm): ~n \le 500~ và ~k \le 20~
• Subtask 6 (~15\%~ điểm): ~n \le 5000~
• Subtask 7 (~10\%~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 2 3
9756

Sample Output 1

2

Sample Input 2

5 3 2
00000

Sample Output 2

6

Giải thích

• Trong ví dụ đầu tiên, có hai cách chia thỏa mãn là ~(9, 756)~ và ~(975, 6)~. Hai cách chia đoạn ~(9756)~ và ~(9, 75, 6)~ không thỏa mãn vì có ít hơn hoặc nhiều hơn hai đoạn, cách chia ~(97, 56)~ không thỏa mãn vì ~97~ không chia hết cho ~3~.
• Trong ví dụ thứ hai, các cách chia thỏa mãn là ~(0, 0, 000)~, ~(0, 000, 0)~, ~(000, 0, 0)~, ~(0, 00, 00)~, ~(00, 0, 00)~ và ~(00, 00, 0)~.