Cho một phương trình có dạng: ~N = ax + by + cxy~. Trong đó ~N, a, b, c~ là các hằng số nguyên cho trước.

Yêu cầu: Hãy tìm tất cả các cặp số nguyên không âm ~(x, y)~ thỏa mãn phương trình trên. Dữ liệu bài toán đảm bảo rằng số lượng cặp nghiệm nguyên của phương trình luôn là một số hữu hạn.

Dữ liệu nhập vào từ bàn phím

• Gồm một dòng duy nhất chứa bốn số nguyên ~N, a, b, c~ cách nhau bởi khoảng trắng.

Kết quả ghi ra màn hình

• Dòng đầu tiên: In ra một số nguyên không âm ~K~, là số lượng cặp nghiệm nguyên không âm tìm được.
• ~K~ dòng tiếp theo: Mỗi dòng in ra một cặp nghiệm ~(x, y)~ cách nhau khoảng trắng. Các cặp nghiệm phải được in ra theo thứ tự tăng dần của giá trị ~x~.

Ví dụ

Input 1

24 -4 2 3

Output 1

3
0 12
2 4
10 2

Giải thích 1: Phương trình có dạng: ~24 = -4x + 2y + 3xy~. Có ~3~ cặp số nguyên không âm ~(x, y)~ thỏa mãn phương trình này là ~(0, 12)~, ~(2, 4)~ và ~(10, 2)~. Các cặp nghiệm đã được in ra theo thứ tự ~x~ tăng dần.

Input 2

24 5 0 5

Output 2

0

Giải thích 2: Phương trình có dạng: ~24 = 5x + 5xy~. Phương trình này vô nghiệm vì vế phải luôn là một số chia hết cho ~5~ (bội của ~5~), trong khi vế trái là ~24~ không chia hết cho ~5~. Do đó số lượng nghiệm là ~0~.

Ràng buộc:

• Các hằng số thỏa mãn: ~1 \le N \le 10^{12}~; ~-10 \le a, b, c \le 10~; ~c \neq 0~.
• Có ~40\%~ số test tương ứng với ~40\%~ số điểm thỏa mãn: ~1 \le N \le 10^6~;
• ~35\%~ số test khác tương ứng với ~35\%~ số điểm thỏa mãn: ~1 \le N \le 10^{12}~ và ~b = 0~;
• ~25\%~ số test còn lại tương ứng với ~25\%~ số điểm thỏa mãn: ~1 \le N \le 10^{12}~.

Cho mảng ~A~ có ~n~ phần tử nguyên dương, hãy chọn một tập con có ít nhất ba phần tử (không cần liên tiếp) của ~n~ phần tử sao cho tổng ba số bất kỳ trong tập con đã chọn không lớn hơn tổng các số còn lại trong mảng ~A~ và số lượng phần tử của tập con là lớn nhất.

INPUT

Dòng đầu tiên ghi số ~n~ (~4 \le n \le 10^4~)

Dòng tiếp theo ghi ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ (~A_i \le 10^2~)

OUTPUT

Dòng duy nhất ghi số lượng phần tử được chọn

Nếu không thể chọn được tập con thoả mãn thì in ra ~0~

SAMPLE INPUT

8
6 9 4 3 7 2 5 1

SAMPLE OUTPUT

7

Giải thích: Các phần tử được chọn là ~6, 4, 3, 7, 2, 5, 1~

Cho một dãy ~a~ gồm ~n~ phần tử và số nguyên dương ~k~, hãy đếm số cặp ~(i,j)~ thỏa mãn ~i < j~ và ~a_i + a_j \le k~.

Input

• Dòng đầu chứa ~2~ số nguyên dương ~n~ và ~k~ ~(1 \le n \le 10^5, 1 \le k \le 10^9)~.
• Dòng thứ hai gồm ~n~ phần tử nguyên dương miêu tả dãy ~a~. ~(1 \le a_i \le 10^6)~

Output

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

Giới hạn:

• Subtask 1 (~50\%~ số điểm): ~n \le 5000~
• Subtask 2 (~50\%~ số điểm): ~n \le 10^5~

Sample Input 1

4 6
1 3 5 6

Sample Output 1

2

Sample Input 2

6 8
1 2 5 3 4 8

Sample Output 2

9

Viết liền các số nguyên dương liên tiếp, từ nhỏ đến lớn, bắt đầu từ ~1~, ta sẽ được một dãy dài vô hạn gồm các chữ số: ~123456789101112131415161718192021222324252627282930313233343536\ldots~

Bạn được cho số nguyên dương ~k~, nhiệm vụ của bạn là tìm chữ số thứ ~k~ của dãy trên.

Input

• Dòng thứ nhất chứa số nguyên dương ~T~ - số bộ dữ liệu. (~T \leq 10^3~)
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~.

Output

• In ra ~T~ dòng, mỗi dòng chứa một chữ số cho bộ dữ liệu tương ứng.

Subtasks

• Subtask 1 (~20\%~ số điểm): Mọi số ~k \leq 50~.
• Subtask 2 (~30\%~ số điểm): Mọi số ~k \leq 10^6~.
• Subtask 3 (~50\%~ số điểm): Mọi số ~k \leq 10^{18}~.

Sample Test

Input

5
8
18
16
14
19

Output

8
1
1
1
4