Tèo muốn nổ hũ đầu năm, nhưng anh ấy lại không có tiền để chơi. Thay vào đấy, anh ấy tình cờ tìm thấy được ~1000~ bao lì xì ngay trước cửa nhà, mỗi bao lì xì có trị giá trong khoảng từ ~0~ – ~100k~. Tuy nhiên, để test thử vận may, Tèo sẽ chỉ chọn ~10~ trong số ~1000~ bao lì xì. Là một người bạn mà Tèo tin tưởng nhất, hãy giúp Tèo chọn các bao lì xì để được nhiều tiền nhất!!

Input

• Không nhập gì cả.

Output

• In ra đúng ~10~ số nguyên trong khoảng ~[1, 1000]~ được ngăn bởi dấu cách, số có thể không phân biệt.

Note

Cụ thể, cho một dãy số nguyên dương ~lucky~ có độ dài ~1000~, mỗi phần tử trong dãy được phân phối ngẫu nhiên như sau:

Điểm tối đa của bài này là ~100~ với cách tính điểm:

Gọi ~10~ số nguyên dương mà bạn đưa ra là ~x_1, x_2, ..., x_{10}~. Tổng giá trị mà bạn nhận được là ~S =\sum_{1}^{10}lucky_{x_i}~, khi đó bạn sẽ được ~3 * S^{0.6}~ điểm.

Đêm nay là hôm giao thừa, Tèo muốn canh để bật rickroll vào lúc ~0h~ sáng . Bây giờ là ~23~ giờ ~a~ phút ~b~ giây, và đoạn rickroll của anh bắt đầu sau ~s~ phút ~t~ giây tính từ lúc Tèo mở, hỏi anh ấy có thể bật video đầu năm cho cả nhà hay đã trễ quá rồi.

Input

• Dòng đầu tiên nhập vào số ~T~ là số lượng test ~(1 \leq T \leq 10^5)~.

• ~T~ dòng sau, mỗi dòng nhập ~4~ số nguyên ~a, b, s, t~ ~(0 \leq a, b, s, t \leq 59)~.

Output

• Gồm ~T~ dòng, mỗi dòng in ra "Yes" hoặc "No" (không có ngoặc kép) nếu Tèo có thể canh để bật rickroll vào lúc ~0h~ sáng và ngược lại.

Sample Input 1

1
58 57 1 2

Sample Output 1

Yes

Sample Input 2

1
58 57 2 5

Sample Output 2

No

Note

Với test ví dụ thứ nhất, Tèo có thể mở video vào lúc ~23~ giờ ~58~ phút ~58~ giây. Vì bây giờ là ~23~ giờ ~58~ phút ~57~ giây nên anh vẫn còn kịp 1 giây để bật video.

Với test ví dụ thứ hai, Tèo có thể mở video vào lúc ~23~ giờ ~57~ phút ~55~ giây. Vì bây giờ là ~23~ giờ ~58~ phút ~57~ giây nên anh đã quá trễ để rickroll cho cả nhà.

Tèo chuẩn bị về quê ăn tết, nhưng Tèo còn chưa làm xong bài tập thầy giao. Tèo đang có ~n~ bài tập còn đang dở, bài thứ ~i~ anh ấy biết chắc rằng mình sẽ hoàn thành trong ~t_i~ phút và sẽ được ~v_i~ điểm. Các bài được sắp xếp theo độ khó giảm dần, do Tèo có sở thích làm bài khó thì giỏi còn bài dễ thì ngu nên với mỗi cặp ~(i, j)~ sao cho ~i \leq j~ thì ~t_i \leq t_j~ và ~v_i \geq v_j~.

Vì gần đến deadline rồi nên Tèo muốn giải bài tập để được nhiều điểm nhất có thể. Câu hỏi của Tèo như sau: Nếu chỉ còn ~x~ phút thì Tèo sẽ chọn các bài để làm như thế nào sao cho được nhiều điểm nhất.

Input

• Dòng đầu tiên nhập số ~n~ ~(1 \leq n \leq 10^5)~ là số bài Tèo được giao.

• Dòng thứ ~2~ gồm ~n~ số nguyên dương ~t_1,t_2,...,t_n~ ~(1 \leq t_i \leq 10^9)~ với ~t_i~ là thời gian Tèo làm bài tập của bài thứ ~i~.

• Dòng thứ ~3~ gồm ~n~ số nguyên dương ~v_1,v_2,...,v_n~ ~(1 \leq v_i \leq 10^9)~ với ~v_i~ là số điểm của bài thứ ~i~.

• Dòng thứ ~4~ gồm số ~Q~ ~(1 \leq Q \leq 10^5)~ là số lượng câu hỏi mà Tèo đặt ra.

• ~Q~ dòng tiếp theo, dòng thứ ~i~ gồm số nguyên dương ~x_i~ ~(1 \leq x_i \leq 10^{14})~ là lượng thời gian Tèo có cho câu hỏi thứ ~i~.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ là đáp số cho câu hỏi thứ ~i~.

Sample Input

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

Sample Output

12
0

Note

Với test ví dụ trên:

• Khi Tèo còn ~8~ phút, anh có thể làm bài ~3~ bài đầu tiên, khi đó điểm mà Tèo nhận được là ~5 + 4 + 3 = 12~ và mất ~2 + 2 + 3 = 7~ phút. Có thể chứng minh đây là cách làm tối ưu.
• Khi Tèo còn ~1~ phút, anh không thể làm bài nào hết trong ~5~ bài thầy giao, vì thể điểm của anh là ~0~.

Constraint

Trong giờ học, Tèo được biết đến tới khái niệm xâu đối xứng. Một xâu đối xứng là một xâu khi đọc từ trái qua phải hay ngược lại đều như nhau. Nhưng vì định nghĩa quá nhàn đối với anh, Tèo quyết định sẽ xào nấu thêm một chút. Tèo định nghĩa một xâu ~t~ là đẹp nếu ~t~ là một xâu đối xứng và biểu diễn số của t chia hết cho 2, chia hết cho 3 và chia hết cho 5.

Ví dụ các xâu đẹp: ~01233210, 030, 0000~ (Có thể có các chữ số ~0~ thừa ở đầu xâu)

Cho một xâu kí tự ~s~ gồm các chữ số ~0~ đến ~9~. Hãy giúp tèo đếm có bao nhiêu cặp ~(l, r)~ ~(l \leq r)~ sao cho xâu ~s_l s_{l+1} ... s_r~ đẹp. Sau một hồi suy nghĩ thì Tèo nghĩ mình có thể nấu quá cháy nên không tìm được cách giải. Vì thế, anh nhờ bạn giải giúp bài toán siêu khó của Tèo này.

Input

• Gồm một dòng duy nhất chứa xâu kí tự ~s~ ~(|s| \leq 5 \cdot 10^3)~.

Output

• In ra kết quả của bài toán.

Sample Input

030

Sample Output

3

Note

Các cặp ~(l, r)~ thỏa mãn là ~(1, 1)~, ~(3, 3)~, ~(1, 3)~. Vì vậy, đáp án là ~3~.

Constraint

Tèo đang có một dãy ~a~ gồm ~n~ số nguyên dương. Nhân dịp năm mới, Tèo chuẩn bị quay lô tô để farm (đốt) tiền, nhưng anh không biết sẽ chọn số nào để đặt. Thay vào đó, Tèo quyết định sẽ dùng dãy a để chọn giúp anh, Tèo định nghĩa một cặp ~(i, j)~ ~(i < j)~ là may mắn khi ~a[i] \cdot a[j]~ là số chính phương và ~a[i] + a[j] \leq x~. Nhưng trước hết, Tèo nhờ bạn đếm xem trong dãy ~a~ có bao nhiêu cặp may mắn.

Input

• Dòng đầu nhập vào hai số ~n~, ~x~ ~(n \leq 10^5, x \leq 2 \cdot 10^6)~.

• Dòng thứ hai nhập ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(a_i \leq 10^6)~.

Output

• In ra kết quả của bài toán

Sample Input

6 5
3 1 4 3 2 1 

Sample Output

3

Note

Các cặp thỏa mãn là ~(2,3),(2,6),(3,6)~. Vì vậy, đáp án là ~3~.

Constraint

Vì học toán rất ngu nên Tèo chỉ biết ~3~ số đầu trong dãy lũy thừa lủa ~3~, đó là ~1~, ~3~, ~9~. Anh đang thắc mắc rằng liệu có số nào lớn hơn trong dãy hay không, vì vậy Tèo liền nảy ra một ý tưởng càng ngu hơn bằng cách viết lên bảng một số ~N~ rất lớn, và tự hỏi xem số này có phải lũy thừa của ~3~ hay không, hãy giúp Tèo thực hiện ý tưởng của anh!

Input

• Dòng đầu tiên nhập vào ~T~ là số lượng truy vấn.

• ~T~ dòng sau, mỗi dòng nhập vào một số ~N~ ~(N \leq 10^{1000000})~.

Output

• Với mỗi truy vấn, in ra "Yes" hoặc "No" (không ngoặc kép) nếu ~N~ là lũy thừa của ~3~ và ngược lại.

Sample Input

2
9
2

Sample Output

Yes
No

Note

Lũy thừa của ~3~ là số có dạng ~3^x~ ~(x \geq 0)~.

VD: ~3^0 = 1~, ~3^1 = 3~, ~3^2 = 9~.

Constraint

Lưu ý: Bản không dễ và bản dễ chỉ khác nhau bởi giới hạn ~n~ và điệu kiện của cặp ~(l, r)~

Trong giờ học, Tèo được biết đến tới khái niệm xâu đối xứng. Một xâu đối xứng là một xâu khi đọc từ trái qua phải hay ngược lại đều như nhau. Nhưng vì định nghĩa quá nhàn đối với anh, Tèo quyết định sẽ xào nấu thêm một chút. Tèo định nghĩa một xâu ~t~ là đẹp nếu ~t~ là một xâu đối xứng và biểu diễn số của t chia hết cho 2, chia hết cho 3 và chia hết cho 5.

Ví dụ các xâu đẹp: ~01233210, 030, 0000~ (Có thể có các chữ số ~0~ thừa ở đầu xâu)

Cho một xâu kí tự ~s~ gồm các chữ số ~0~ đến ~9~. Hãy giúp tèo đếm có bao nhiêu cặp ~(l, r)~ ~(l \leq r)~ sao cho xâu ~s_l s_{l+1} ... s_r~ đẹp và có độ dài lẻ. Sau một hồi suy nghĩ thì Tèo nghĩ mình có thể nấu quá cháy nên không tìm được cách giải. Vì thế, anh nhờ bạn giải giúp bài toán siêu khó của Tèo này.

Input

• Gồm một dòng duy nhất chứa xâu kí tự ~s~ ~(|s| \leq 2 \cdot 10^5)~.

Output

• In ra kết quả của bài toán.

Sample Input

030

Sample Output

3

Note

Các cặp ~(l, r)~ thỏa mãn là ~(1, 1)~, ~(3, 3)~, ~(1, 3)~. Vì vậy, đáp án là ~3~.

Định nghĩa số fibo cấp ~x~ bằng công thức sau:

~F_{x, 0}, F_{x, 1}, ..., F_{x, x - 1} = 1~.

~F_{x, i} = \sum_{j = i - (x - (i \; mod \; x))}^{i - 1}F_{x, j}~.

Cho ~2~ số ~n~ và ~x~, bạn cần tìm ~F_{x, n}~ là số fibo cấp ~x~ thứ ~n~ modulo ~10^9+7~.

Input

• Nhập ~2~ số nguyên dương ~n~ và ~x~ ~(n \leq 10^{18}, x \leq 100)~.

Output

• In ra ~F_{x, n}~ modulo ~10^9+7~.

Sample Input 1

10 3

Sample Output 1

56

Sample Input 2

420 69

Sample Output 2

464694677

Note

Khi ~x = 3~, ~11~ số đầu của dãy fibo cấp ~3~ là ~1,1,1,3,4,4,11,15,15,41,56~.

Constraint