Cho phương trình bậc ba ~ax^3+bx^2+cx+d=0~ với ~a,b,c,d~ là các số nguyên có trị tuyệt đối không vượt quá ~10^4~ và ~a \neq 0, \, d \neq 0.~ Yêu cầu đặt ra là in ra các nghiệm nguyên (nếu có) của phương trình này.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ cho biết số lượng phương trình cần xét, trong đó ~1 \le n \le 10^5~. Với mỗi dòng tiếp theo sẽ gồm ~4~ số ~a,b,c,d~ thỏa mãn ràng buộc như đề bài.

Output

Với mỗi phương trình, nếu nó không có nghiệm nguyên thì in ra NO; nếu có nghiệm nguyên thì in ra các nghiệm đó, theo thứ tự từ nhỏ đến lớn.

Sample input 1

1
1 1 1 2

Sample output 1

NO

Sample input 2

2
1 1 1 1
1 -6 11 -6

Sample output 2

-1
1 2 3

Giải thích phương trình ~x^3+x^2+x+2=0~ không có nghiệm nguyên, còn phương trình ~x^3+x^2+x+1=(x+1)(x^2+1)=0~ có nghiệm nguyên duy nhất là ~x=-1~, còn phương trình ~x^3-6x^2+11x-6=(x-1)(x-2)(x-3)=0~ có ba nghiệm ~x=1,2,3~.

Subtasks:

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

Nhận thấy các con của mình rất chăm học thuật toán nên bố Tài SC (super cute) đã ra cho chúng một bài toán ngây thơ như sau: cho ~q~ số nguyên dương (không nhất thiết phân biệt), hãy tính tổng ước của từng số. Các con cảm thấy rất giận dỗi vì lại ra một bài căn bản như thế, cho đến khi chúng đọc được kỹ các subtask, hãy làm thử bài toán này của bố Tài nhé.

Input

Dòng đầu tiên là số nguyên dương ~q~.

Dòng tiếp theo là ~q~ số nguyên dương ~a_1, a_2, ..., a_q.~

Output

In ra ~q~ số là đáp số của bài toán.

Sample input

4
2 4 10 9

Sample output

3 7 18 13

Subtasks

• Subtask 1 (15% số điểm): ~q ≤ 10^4; a_i ≤ 10^3~ với ~(1 ≤ i ≤ q)~
• Subtask 2 (25% số điểm): ~q ≤ 10^5; a_i ≤ 10^5~ với ~(1 ≤ i ≤ q)~
• Subtask 3 (35% số điểm): ~q ≤ 10^5; a_i ≤ 10^6~ với ~(1 ≤ i ≤ q)~
• Subtask 4 (25% số điểm): ~q ≤ 10^6; a_i ≤ 10^{12}~ và ~a_{i+1} = a_i + 1~ với ~1 ≤ i <q.~</li>

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.

Bố Tài Super Cute hôm nay lại cho các con zai yêu một bài toán vui. Bố viết một dãy ~n~ số nguyên dương ~x_1, x_2, ..., x_n~ và đặt ra ~m~ câu hỏi. Với mỗi câu, bố cho hai số nguyên dương ~L, R~ và với từng số nguyên tố ~p~ thuộc đoạn ~[L;R]~, bố muốn tính số lượng bội của ~p~ có trong dãy đã cho, sau đó cộng hết các kết quả lại với nhau. Bạn hãy đóng vai làm con zai yêu của bố Tài super cute để giải quyết bài toán này nhé.

Input

• Dòng đầu tiên chứa số nguyên ~n~ với ~1≤ n ≤ 10^5.~
• Dòng thứ 2 chứa ~n~ số nguyên dương ~x_1, x_2, …, x_n~ với ~2 ≤ x_i ≤ 10^7~
• Dòng thứ 3 chứa số nguyên ~m~ với ~1 ≤ m ≤ 50000~. Mỗi dòng ~i~ trong ~m~ dòng sau chứa 2 số nguyên ngăn cách bởi 1 dấu cách ~L, R~ với ~2 ≤ L ≤ R ≤ 2.10^9~.

Output

• Gồm m dòng, mỗi dòng 1 số nguyên là câu trả lời cho một truy vấn.

Sample input

6
5 5 7 10 14 15
3
2 11
3 12
4 4

Sample output

9
7
0

Giải thích: trong câu hỏi 1, ta thấy có các số nguyên tố ~2,3,5,7,11~ trong đoạn đã cho. Ta tính được lần lượt có: ~2,1,4,2,0~ bội của chúng trong dãy, vì thế tổng cần tìm là ~9~. Tương tự với các câu hỏi khác.

Subtask

• Sub1: 30% test có ~0 < n, m ≤ 2.10^3, 2 ≤ L ≤ R ≤ 10^3.~
• Sub2: 30% test có ~0 < n, m ≤ 2.10^3, 2 ≤ L ≤ R ≤ 10^6.~
• Sub3: 40% test có ràng buộc như đề bài đã mô tả.

Hôm nay Ban được học về số palindrome, đó là số mà nếu viết biểu diễn thập phân của nó (không có chữ số 0 ở đầu) ở dạng ngược lại thì ta vẫn được cùng một số. Ví dụ 1221 là một số palindrome trong khi 123 thì không phải. Ban tò mò không biết trong đoạn từ ~L~ tới ~R~ có tất cả bao nhiêu số palindrome mà tổng các chữ số ở dạng thập phân của nó là số nguyên tố. Bạn hãy giúp Ban nhé.

Input Gồm một dòng duy nhất chứa hai số nguyên ~L~ và ~R~ với ~1≤ L≤ R≤10^{12}.~

Output

Một số nguyên duy nhất là số lượng số palindrome mà tổng chữ số ở dạng thập phân của nó là số nguyên tố trong đoạn ~[L,R].~

Sample input

10000 12000

Sample output

9

Giải thích

Có ~9~ số đó là ~10001,10101,10301,10501,10901,11111,11311,11711,11911.~

Subtasks

• Subtask 1 (60% số điểm): ~L,R≤10^6.~
• Subtask 2 (40% số điểm): ~L,R≤10^{12}.~

Một số ~M~ đươc gọi là liên kết với ~X~ nếu ~M~ ~XOR~ ~X~ ~>~ ~M~ ~AND~ ~X~. Cho trước một mảng ~n~ số nguyên và ~q~ truy vấn. Mỗi truy vấn được cho bởi bộ 3 số ~L, R~ và ~X~. Yêu cầu đếm xem trong đoạn từ ~L~ đến ~R~ có bao nhiêu số liên kết với ~X~.

Input

Dòng đầu chứa số nguyên ~n \le 2.10^5~, dòng tiếp theo chứa ~n~ số nguyên là các phần tử của mảng gồm các số nguyên dương không vượt quá ~10^9~, dòng thứ ba chứa số nguyên ~q~ là số truy vấn.

Trong ~q~ dòng cuối cùng, mỗi dòng chứa 3 số nguyên ~L, R~ và ~X~ biểu thị truy vấn.

Output

~Q~ dòng là kết quả cho từng truy vấn.

Sample input

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

Sample output

3
2

Subtasks

• Subtask 1: 50% số test có ~n~ và ~q \le 2000~.
• Subtask 2: 50% số test còn lại có ~n~ và ~q \le 200000.~