Kỳ thi học sinh giỏi sắp đến, Thảo luyện tập các phép cộng để rèn luyện trí tuệ. Thảo có một trò chơi như sau: Có một số nguyên dương N, phải cộng liên tiếp các số N cho tới khi tất cả các chữ số của tổng nhận được đều bằng nhau. Ví dụ N = 74 thì anh ấy cần cộng 3 số 74 để nhận được tổng là 222 có các chữ số giống nhau.

Hãy viết chương trình tính số lần cộng với một số nguyên dương N để được giải quyết vấn đề trên

Input

• Một số nguyên dương n (n < 1000)

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số lượng số cần cộng. Trường hợp số n đã gồm các chữ số giống nhau chỉ cần ghi số 1, trường hợp không tồn tại tổng có các chữ số giống nhau ghi -1

Scoring

• Subtask 1 (40% số điểm): só lần cộng không vượt quá 1.000.000
• Subtask 2 (60% số điểm): không có ràng buộc nào thêm

Thảo đang rảnh. Anh ấy đã được đưa đi nghỉ trong ~n~ ngày. Thảo đã mơ ước được đến một khu nghỉ mát trượt tuyết từ lâu, vì vậy anh muốn dành vài ngày liên tục để đi trượt tuyết. Vì kỳ nghỉ đòi hỏi sự chuẩn bị kỹ lưỡng nên anh ấy sẽ chỉ đi ít nhất ~k~ ngày. Bạn được cho một mảng ~a~ chứa dự báo thời tiết tại khu nghỉ mát. Tức là ngày thứ ~i~ nhiệt độ sẽ là ~a~_i độ. Thảo sinh ra ở Việt Nam nên anh ấy chỉ đi nghỉ nếu nhiệt độ không quá ~q~ độ trong cả kỳ nghỉ. Thảo nhờ bạn giúp anh ấy đếm số cách để chọn ngày đi nghỉ tại khu nghỉ dưỡng.

Input;

• Dòng 1 chứa số nguyên T (1 ≤ T ≤ 10) là số test case

• Tại mỗi test_case:

  • Dòng 1 là 3 số ~n~, ~k~, ~q~. (1 ≤ ~n~ ≤ 2.10⁵, 1 ≤ ~k~ ≤ n, -10⁹ ≤ ~q~ ≤ 10⁹)
  • Dòng 2 là mảng ~a~ gồm ~n~ phần tử là nhiệt độ của ~n~ ngày.

Output

• Mỗi dòng là kết quả mỗi test case

SAMPLE INPUT

3
3   1   15
-5  0   -10
5   3   -33
8   12  9   0   5
4   3   12
12  12  10  15

SAMPLE OUTPUT

6
0
1

Giải thích

• Test 1: Bộ các ngày thỏa mãn là: [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]
• Test 2: Vì nhiệt độ các ngày đều lớn hơn q nên không có lịch trình thỏa mãn
• Test 3: [1, 2, 3]

Một con đom đóm bay vào một cái hang đầy những chướng ngại vật gồm: măng đá (nhô lên từ mặt đất) và nhũ đá (đâm xuống từ trần hang). Hang này dài N đơn vị (N chẵn) và cao H đơn vị. Khi vào hang, vật cản đầu tiên là măng đá, sau đó là nhũ đã, rồi lại đến măng đá, ... cứ thế thay phiên nhau.

Đây là một ví dụ về một hang dài 14 đơn vị và cao 5 đơn vị.

Con đom đóm này không phải là loài có thể bay quanh các chướng ngại vật. Thay vào đó, nó sẽ chọn một mức chiều cao bắt đầu rồi bay từ đầu đến cuối hang, phá hết tất cả các chướng ngại vật trên đường bay của nó.

Theo ví dụ trên, nếu chọn mức 4, con đom đóm sẽ phá tất cả là 8 chướng ngại vật.

Đây không phải là lựa chọn tốt nhất vì con đom đóm sẽ ít mệt hơn nếu chọn mức 1 hoặc mức 5, lúc này nó chỉ cần phá 7 chướng ngại vật.

Bạn được cho chiều dài, chiều cao và kích thước của tất cả các chướng ngại vật. Hãy xác định số chướng ngại vật tối thiểu mà con đom đóm cần phá để thoát khỏi hang, và có bao nhiêu cách chọn khác nhau đưa đến kết quả đó.

Dữ liệu

• Dòng 1: Hai số nguyên N và H (1 ≤ N ≤ 2.105 và 1 ≤ H ≤ 5.105) là chiều dài và chiều cao của hang.
• Mỗi dòng trong N dòng tiếp theo là một số nguyên dương - kích thước của chướng ngại vật. Tất cả các kích thước đều nhỏ hơn H.

Kết quả

Gồm 2 số nguyên cách nhau là số chướng ngại vật ít nhất cần phá và số cách chọn khác nhau để có được kết quả đó.

Giới hạn

Trong tối đa là 1/3 số test, N * H không vượt quá 106.

SIMPLE INPUT

6 7
1
5
3
3
5
1

SIMPLE OUTPUT

2 3