Cho hai số nguyên dương \(L,R\). Hãy đếm xem có bao nhiêu số nguyên dương \(x\) thuộc đoạn [\(L,R\)] chia hết cho 19; sao cho ở dạng biểu diễn thập phân, \(x\) không chứa hai chữ số nào có tổng chia hết cho \(3\).

Input

• Dòng đầu chứa số nguyên dương \(T\) là số lượng testcase (\(1 ≤ T ≤ 10^5\));
• Mỗi test được mô tả trên hai dòng là \(L\) và \(R\) (\(1 ≤ L ≤ R ≤ 10^{10000}\)).

Output

• Với mỗi testcase, ghi trên một dòng số lượng số nguyên dương \(x\) tìm được, sau khi chia lấy dư cho \(1000000007\)

Scoring

• Có 50% số test với \(R ≤ 10^6\);
• Có 30% số test với tổng độ dài của tất cả các số \(R\) trong \(T\) testcase không vượt quá \(10^3\);
• Có 20% số test với ràng buộc gốc.

Example

2
1 100
101 200

4
2

Xếp hình là một trong những trò kinh điển thời tuổi thơ dữ dội của chúng ta. Trò chơi gồm một bảng \(3 × 3\) chứa 8 miếng ghép và một ô trống. Người chơi cố gắng sắp xếp lại các miếng ghép thành một thứ tự định sẵn, bằng cách lặp lại việc di chuyển một trong các miếng ghép kề cạnh với ô trống vào ô trống (và dĩ nhiên ô trống sẽ chuyển sang vị trí của miếng ghép). Để đơn giản, các miếng ghép được đánh số từ 1 đến 8 và thứ tự định sẵn được cho trong hình sau:

Ở phiên bản khó của trò chơi, bạn cần tìm số bước di chuyển ít nhất để đưa trạng thái đã cho về trạng thái định sẵn. Hùng đã chơi trò này nhiều lần nhưng vẫn gặp vấn đề với phiên bản khó, và có vẻ bài tập này được thiết kế để dành riêng cho cậu.

Input

• Dòng đầu chứa số nguyên dương \(T\) là số lượng testcase;
• \(T\) dòng tiếp theo mỗi dòng chứa 9 số nguyên là một hoán vị của \(0, 1, 2, . . . , 8\) mô tả một trạng thái bắt đầu. Các số trong hoán vị lần lượt là các số ghi trên các ô của bảng, theo thứ tự từ trái sang phải, từ trên xuống dưới. Số 0 đại diện cho ô trống.

Output

• Gồm \(T\) dòng, mỗi dòng ghi một số nguyên là số bước di chuyển ít nhất, hoặc -1 nếu không thể đưa trạng thái này về trạng thái định sẵn.

Scoring

• Trong tất cả các test: \(T ≤ 10^6\);
• 30% test với \(T = 5\) và kết quả không vượt quá 10;
• 30% test tiếp theo có kết quả không vượt quá 10;
• 40% test tiếp theo với ràng buộc gốc.

Example

4 
0 1 2 3 4 5 6 7 8 
3 1 2 0 4 5 6 7 8 
1 2 3 4 5 6 7 8 0 
2 3 0 4 1 5 8 6 7

0 
1 
22 
-1

Vương quốc có \(n\) thành phố và \(n-1\) con đường hai chiều, đảm bảo đi lại giữa mọi cặp thành phố. Thành phố x được gọi là quản lý \(y\) nếu \(x\) nằm trên đường đi đơn từ \(y\) đến 1. Sản lượng lương thực tại thành phố \(x\) là \(w_x\). Quốc vương muốn chọn ra một đỉnh để xây dựng kho dự trữ, chi phí vận chuyển lương thực nếu xây dựng kho dự trữ tại \(u\) là \(∑_{v=1}^n {w_v×d(v,u)}\) với \(d(v,u)\) là số cạnh trên đường đi đơn từ \(v\) đến \(u\).

Có \(Q\) thay đổi cho sản lượng được báo cáo, mỗi thay đổi có dạng \(1\ u\ c\) hoặc \(2\ u\ c\) tương ứng là tăng \(w_u\) lên \(c\) đơn vị hoặc tăng \(w_v\) lên \(c\) đơn vị với mọi \(v\) quản lý bởi \(u\). Sau mỗi thay đổi, cần tìm đỉnh \(u\) để xây dựng kho dữ trữ sao cho tổng chi phí vận chuyển lương thực là nhỏ nhất, nếu có nhiều \(u\) như vậy thì chọn \(u\) nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(Q\);
• Dòng thứ hai chứa \(n\) số \(w_1,w_2,...,w_n\);
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa hai số \(u\ v\) mô tả một cạnh của cây;
• Mỗi dòng trong số \(Q\) dòng tiếp theo chứa ba số \(t\ u\ c\) mô tả một thay đổi

Output

• Ghi \(Q\) dòng là chỉ số của đỉnh được chọn sau thay đổi thứ \(Q\).

Scoring

• Trong tất cả các test: \(n,Q ≤ 10^5; 1 ≤ w_i ≤ 10^6; |c| ≤ 10^6.\)
• Có 12% số test với \(n,Q ≤ 5000\);
• Có 16% số test có cạnh nối từ \(x\) đến \(x - 1\) với mọi \(2 ≤ x ≤ n;\)
• Có 16% số test có cạnh nối từ \(x\) đến \([x/2]\) với mọi \(2 ≤ x ≤ n;\)
• Có 20% số test không có thay đổi loại 2;
• Có 36% số test với ràng buộc gốc. uộc gốc

Example

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

2 
2 
1