Số square-free là số nguyên dương không có ước lớn hơn ~1~ nào là số chính phương cả. Chẳng hạn ~1,10,15,30~ là square-free nhưng ~12,18,25~ thì không. Cho hai số nguyên dương ~L, R~ với ~1 \le L \le R \le 10^7~, yêu cầu đếm số lượng số square-free lớn hơn ~1~, chỉ có ước nguyên tố lấy trong đoạn từ ~L~ đến ~R~.

Input

Dòng đầu tiên gồm số ~t~ là số test với ~1 \le t \le 3.~

Các dòng tiếp theo gồm các cặp ~(L,R)~.

Output

Ứng với mỗi test, cho biết số lượng số square-free thỏa mãn, vì kết quả có thể rất lớn nên lấy modulo ~10^9 + 7.~

Sample input

2
1 4
20 25

Sample output

3
1

Giải thích trong VD1, các số square-free thỏa mãn là: ~2,3,6~, còn trong VD2, chỉ có ~23~ thỏa mãn.

Trong một hội nghị cấp cao của CLB H3.2, có tất cả ~n~ SV và mỗi người sẽ biết một vài ngôn ngữ lập trình. Thư ký Luna ghi nhận được có tất cả ~m~ cặp trong số họ có biết chung ngôn ngữ lập trình và có thể "chém gió trực tiếp" được với nhau. Độ danh tiếng của một người ~X~ là số lượng người mà ~X~ có thể chém gió trực tiếp được. Tất nhiên sẽ có những người ~A, B~ cũng muốn "chém gió gián tiếp" nếu như thỏa mãn điều kiện: có thể xếp họ ngồi vào một dãy ghế mà ~A~ đầu dãy này, ~B~ đầu dãy kia và ở giữa là vài người khác sao cho hai người ngồi cạnh nhau trên ghế thì có thể "chém gió trực tiếp" được.

Hãy đếm số cặp ~(A,B)~ là những người có cùng độ danh tiếng và ~A,B~ có thể chém gió trực tiếp hoặc gián tiếp với nhau.

Input

Dòng đầu tiên gồm số nguyên dương ~n, m~ với ~2 \le n \le 10^5~ và ~0 \le m \le 3.10^5.~

Dòng tiếp theo gồm các cặp số ~(a,b)~ với ~1 \le a \neq b \le n~ cho biết số thứ tự của những người có thể chém gió trực tiếp được. Do thư ký Luna cũng hơi lẩm cẩm nên một cặp có thể bị xuất hiện nhiều lần.

Output

Đáp số của bài toán.

Sample input 1

3 2
1 2
2 3

Sample output 1

1

Sample input 2

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

Sample output 2

10

Giải thích: trong VD1 đã cho, hai người thứ 1 và 3 có thể chém gió gián tiếp thông qua 2 và họ cùng độ danh tiếng là 1 nên ~(1,3)~ thỏa mãn điều kiện.

Subtasks:

• Có 50% số test ứng với ~n \le 10^4.~
• Có 50% số test không có ràng buộc nào thêm.

Anh Long là một đại ca máu lạnh khét tiếng của IUH, anh sống trong một tòa lâu đài rộng lớn với thú cưng là các con vịt. Anh Long nuôi bầy vịt trong một căn phòng hình chữ nhật khép kín và ngăn vách cho chúng tạo thành các phòng nhỏ. Mỗi đêm, để vịt có sự riêng tư, anh cho mỗi con ngủ trong một phòng. Hệ thống vách tường của căn phòng của vịt được mô tả như sau: góc dưới-trái là (0,0) và góc trên-phải là ~(A,B)~ và

• Có ~m~ bức tường ngang được mô tả bởi đoạn thẳng nối điểm ~(0,b_i)~ với ~(A,b_i)~ ở đây ~0<b_i<B~ với mọi ~i=1,2,…,m~. </li>
• Có ~n~ bức tường dọc được mô tả như là các đoạn thẳng nối điểm ~(a_i,0)~ với ~(a_i,B)~ ở đây ~0<a_i<A~ với mọi ~i=1,2,…,n~. </li>
• Chu vi của hình chữ nhật cũng là các bức tường, như vậy căn phòng sẽ được chia thành ~(m+1)×(n+1)~ phòng nhỏ.

Đến ban ngày, để lũ vịt đỡ cô đơn, anh sẽ dùng hệ thống tự động mở một số đoạn tường ngang hoặc dọc của một số phòng sao cho tất cả các phòng đều đi đến được nhau. Hãy tính tổng độ dài bé nhất của các đoạn tường mà anh Long tháo để có thể làm được điều trên?

Input

• Dòng đầu tiên chứa 4 số nguyên dương ~A,B,n,m~ với ~1≤A,B≤10^9~ và ~n,m≤ 25000~.
• Trong ~n~ dòng tiếp theo lần lượt chứa các số nguyên ~a_1,a_2,…,a_n~ và ~m~ dòng cuối cùng lần lượt chứa các số nguyên ~b_1,b_2,…,b_m~.

Output

Một số nguyên duy nhất là tổng độ dài nhỏ nhất của các đoạn tường cần phá.

Sample input

15 15 5 2
2
5
10
6
4
11
3

Sample output

44

Subtasks:

• Subtask 1: ~n,m≤2000~
• Subtask 2: ~n,m≤25000~

Nhà cô Ban có nuôi một đàn gà đi bộ rất chắc thịt ngọt xương, một loại đặc sản đắt tiền. Đến mùa, cô Ban lại giết thịt để cung cấp các suất ăn dinh dưỡng cho lab H3.2. Đàn gà đi bộ của cô được nuôi nhốt trong chuồng có dạng hình tròn. Bên trong chuồng này có ~n~ căn phòng đánh số theo chiều kim đồng hồ lần lượt là ~1,2,…,n~. Mỗi phòng đều có hai cửa thông sang phòng bên cạnh và một cửa hướng ra bên ngoài để gà đi vào.

Cô Ban muốn bố trí ~r_i~ con gà ở phòng ~i~ với ~i=1,2,..,n~. Để đàn gà đi vào chuồng một cách có trật tự, cô chỉ mở ~k~ trong số ~n~ cánh cửa hướng ra bên ngoài đón các con gà về chuồng. Các con gà sau khi vào một trong ~k~ cửa sẽ di chuyển theo chiều kim đồng hồ đến phòng đầu tiên chưa đủ số gà cần chứa và ở lại phòng này.

Yêu cầu: hãy giúp cô Ban chọn ra ~k~ cửa hướng ra ngoài để tổng đoạn đường di chuyển của tất cả các con gà sau khi đi vào chuồng là nhỏ nhất. Khi con gà di chuyển đến phòng kế tiếp thì nó phải di chuyển 1 đơn vị độ dài.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,k~ với ~3≤n≤100; 1≤k≤7.~
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~r_i~ với ~1≤r_i≤10^6~

Output

Một số nguyên duy nhất là kết quả tìm được.

Sample input

6 2
2
5
4
2
6
2

Sample output

14

Giải thích: cô Ban mở cửa ngoài các phòng ~2~ và ~5~. Khi đó có ~11~ con gà đi vào cửa ~2~ và tổng khoảng cách đi bộ của các con gà này là ~8~ để vào các chuồng ~2, 3, 4~. Có ~10~ con gà đi vào cửa ~5~ và tổng khoảng cách di chuyển của các con gà này là ~6~ để vào các chuồng ~5, 6~ và ~1~.