Với mỗi cặp số nguyên không âm ~a~ và ~b~, ta định nghĩa tổng chữ số của đoạn ~[a, b]~ là tổng của các chữ số xuất hiện khi viết tất cả các số nguyên lớn hơn hoặc bằng ~a~ và nhỏ hơn hoặc bằng ~b~. Ví dụ, tổng chữ số của đoạn ~[49, 52]~ là ~4+9+5+0+5+1+5+2=31~.

Cho hai số nguyên không âm ~a~ và ~b~, hãy viết chương trình tính tổng chữ số của đoạn ~[a, b]~.

Input

• Gồm một dòng chứa hai số nguyên không âm ~a~ và ~b~ (~0 \le a \le b \le 10^{15}~).

Output

• Gồm một dòng chứa số nguyên là tổng các chữ số của đoạn ~[a, b]~.

Example

Sample Input

49 52

Sample Output

31

Bạn cần trả lời ~T~ câu hỏi. Mỗi câu hỏi gồm hai số nguyên ~a,b~, đếm số lượng số nguyên nằm trong đoạn ~[a,b]~ mà chia hết cho ~k~, và tổng các chữ số của chúng cũng chia hết cho ~k~.

Input

• Dòng đầu tiên gồm số nguyên ~T~.
• ~T~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~a,b~ là một câu hỏi.

Output

• Với mỗi câu hỏi, in ra số lượng số thỏa mãn.

Constraints

• ~1 \le T \le 200~.
• ~1 \le a, b \le 10^{12}~.
• ~1 \le k \le 10000~.

Example

Sample Input

1
1 1000 4

Sample Output

64

Cho hai số nguyên ~a~ và ~b~ (~0 < a \le b \le 10^{100}~).
Gọi số tăng tiến là số có các chữ số không giảm (ví dụ ~1111,\,123,\,88999,\dots~).
Hỏi: Có bao nhiêu số tăng tiến trong đoạn ~[a,b]~ (kết quả modulo ~10^9+7~)?

Input

• Dòng đầu tiên chứa số nguyên ~a~.
• Dòng thứ hai chứa số nguyên ~b~.

Output

• Một dòng duy nhất là đáp án.

Example

Sample Input

1
100

Sample Output

54

Cho 3 số nguyên ~A~, ~B~ và ~K~. Hãy đếm số lượng số nguyên trong khoảng ~[A,B]~ thỏa mãn: biểu diễn thập phân của số này chứa ít nhất ~K~ chữ số liên tiếp giống nhau.

Input

• Gồm một dòng chứa ba số nguyên dương ~A, B, K~ (~1 \le A \le B \le 4 \cdot 10^{18}, 1 \le K \le 20~).

Output

• In ra số lượng số hợp lệ.

Example

Sample Input 1

1 100 2

Sample Output 1

10

Sample Input 2

111 133 2

Sample Output 2

11

Số Delta là số mà hiệu của tổng các chữ số ở vị trí lẻ và tổng các chữ số ở vị trí chẵn bằng ~1~.

Ví dụ: số ~2001~ là số Delta, vì ~(2 + 0) - (0 + 1) = 1~.

Ví dụ: số ~3142~ không phải số Delta, vì ~(3 + 4) - (1 + 2) = 4 \neq 1~.

Tìm số lượng số Delta trong đoạn ~[A, B]~.

Input

• Hai số ~A, B~ (~1 \le A \le B \le 10^8~).

Output

• Số lượng số Delta tìm được.

Example

Sample Input 1

1 10

Sample Output 1

1

Sample Input 2

10 100 

Sample Output 2

9

Note

• VD1: Chỉ có 1 số ~Delta~ duy nhất là ~10~
• VD2: Các số ~Delta~ là ~10, 21, 32, 43, 54, 65, 76, 87, 98~.

Cho số nguyên ~x~. Đếm số lượng số ~y~ mà ~L \le y \le R~ và ~x \oplus y \le S~.

Input

• Một dòng gồm 4 số nguyên ~x, L, R, S~.

Output

• In ra số lượng xâu thỏa mãn.

Constraints

• ~1 \le x, L, R, S \le 10^{18}~.

Example

Sample Input

3 2 7 5

Sample Output

4

Một số được gọi là đặc biệt nếu khi thực hiện quá trình sau lặp đi lặp lại thì không bao giờ thu được số ~1~:

• Lấy bình phương các chữ số của số hiện tại, rồi cộng lại để tạo ra số mới.
• Lặp lại bước trên với số mới này.

Ví dụ với số ~2706=2^2+7^2+0^2+6^2=89~ Tiếp tục: ~89, 145, 42, \ldots~

Ta thấy quá trình này không bao giờ cho kết quả là ~1~, nên ~2706~ là một số đặc biệt.

Yêu cầu: Với mỗi cặp số tự nhiên ~L~ và ~R~ (~1 \le L \le R \le 10^{18}~), hãy xác định có bao nhiêu số đặc biệt nằm trong đoạn ~[L, R]~.

Input

• Dòng đầu chứa số nguyên dương ~T~ là số lượng câu hỏi.
• Tiếp đến là ~T~ dòng, mỗi dòng chứa hai số tự nhiên ~L~ và ~R~ biểu thị câu hỏi tương ứng.

Output

Ghi ra ~T~ dòng, mỗi dòng chứa một số nguyên duy nhất là câu trả lời cho câu hỏi tương ứng.

Example

Sample Input

1
2706 2711

Sample Output

6

Đếm tất cả các số trong khoảng ~[L, R]~ mà không chứa bất kỳ xâu con liên tiếp nào có độ dài lớn hơn ~1~ là palindrome trong biểu diễn thập phân của chúng.

Input

• Một dòng gồm hai số nguyên ~L, R~.

Output

• In ra số lượng số thỏa mãn.

Constraints

• ~0 \le L\le R \le 10^{18}~.

Example

Sample Input

10 15

Sample Output

5

Một số được gọi là đẹp nếu nó chia hết cho tất cả các chữ số của nó. Điều này cũng có nghĩa là số trong biểu diễn thập phân của số đẹp không chứa chữ số ~0~.

Đếm số lượng số đẹp trong đoạn ~[L,R]~.

Input

• Một dòng gồm hai số nguyên ~L,R~.

Output

• In ra một số nguyên là số lượng số đẹp.

Constraints

• ~1 \le L \le R \le 10^{18}~.

Example

Sample Input

10 123

Sample Output

18

Bất phương trình tuyến tính là bất phương trình có dạng như sau: $$a_1 \times x_1 + a_2 \times x_2 + \ldots + a_n \times x_n \leq m$$ Trong đó ~a_1~, ~a_2~, ~\ldots~, ~a_n~ lần lượt được gọi là hệ số của ~x_1~, ~x_2~, ~\ldots~, ~x_n~; còn ~m~ được gọi là hệ số tự do.

Một nghiệm của bất phương trình là một bộ giá trị (~x_1~, ~x_2~, ~\ldots~, ~x_n~) = (~b_1~, ~b_2~, ~\ldots~, ~b_n~) mà khi thay vào thỏa mãn bất phương trình trên.

Yêu cầu: Cho ~n~ và các hệ số ~a_1~, ~a_2~, ~\ldots~, ~a_n~, ~m~; hãy đếm số nghiệm nguyên dương của bất phương trình ấy.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~, ~m~ (~n \leq 10~, ~m \leq 10^9~).

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1~, ~a_2~, ~\ldots~, ~a_n~ (~a_i \leq 10~).

Output

• In ra một số nguyên duy nhất là số nghiệm nguyên dương của phương trình, vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~10^9 + 7~.

Scoring

Sample Input 1

5 15
1 2 3 4 5

Sample Output 1

1

Sample Input 2

5 45
1 2 3 2 1

Sample Output 2

79660

Một bài toán trong đại hội Toán-Tin của Thiên hà như sau: Xét các số nguyên dương có dạng ~\overline{a_1a_2...a_n}~ , trong đó ~a_i~ nhận giá trị từ ~1~ đến ~k~. Một đoạn chữ số từ vị trí thứ ~L~ đến vị trí thứ ~L + 9~ được gọi là đoạn hoàn hảo nếu:

1. ~a_L + a_{L+1} + ... + a_{L+9} = 20~;
2. Các chữ số ~a_L, a_{L+1}, ... , a_{L+9}~ có thể chia làm ~2~ nhóm có tổng bằng nhau.

Yêu cầu: Cho ~n, k~ và ~m~ vị trí ~p_1, p_2, ... , p_m~, hãy đếm số lượng số nguyên dương có dạng ~\overline{a_1a_2...a_n}~ (~a_i~ nhận giá trị từ ~1~ đến ~k~) mà có ~m~ đoạn hoàn hảo lần lượt bắt đầu từ ~p_1, p_2, ... , p_m~.

Dữ liệu: Vào từ thiết bị vào chuẩn:

• Dòng đầu gồm bốn số nguyên dương ~n, k, m, D~ (~9 < n \le 50; k \le 9;D \le 10^9~);
• Dòng thứ hai gồm ~m~ số nguyên ~p_1, p_2, ... , p_m~ (~1 \le p_1 < p_2 < ... < p_m \le n - 9~).

Kết quả: Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên ~r~, trong đó ~r~ là phần dư của số lượng số thỏa mãn chia cho ~D~.

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài có ~m = 1~;
• Có 20% số test khác ứng với 20% số điểm của bài có ~m = 2~;
• Có 60% số test còn lại ứng với 60% số điểm của bài có ~m \le 5~.

Ví dụ: