Ngày hôm nay có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko ham ăn muốn đi ăn ~q~ lượt, mỗi lượt từ gian hàng ~l~ đến gian hàng ~r~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Input

• Dòng đầu gồm 2 số ~n, q~.
• ~q~ dòng tiếp theo mỗi dòng thứ ~i~ gồm 2 số ~l_i, r_i~ ~(1 \le l_i \le r_i \le 10^5)~ là lượt đi ăn thứ ~i~.

Output

• In ra ~n~ số ứng với ~n~ cửa hàng là số lần Yuyuko vào gian hàng.

Sample Test

Input:

4 3
1 3
2 4
1 2

Output:

2 3 2 1

Cho số ~n~. Hãy tìm số ~k \le n~ lớn nhất sao cho ~k~ là tích của 3 số nguyên tố liên tiếp.

Input

• Gồm số tự nhiên ~n \le 10^{18}~.

Output

• Gồm duy nhất một số tự nhiên ~k~. Nếu không có số thỏa mãn in ra -1.

Sample Test

Input:

31

Output

30

Cho số tự nhiên ~n~, hãy đếm bộ 3 số nguyên dương ~(a, b, c)~ sao cho ~a \times b \times c \le n~. Lưu ý ~(a, b, c)~ khác với ~(a, c, b)~ và tương tự.

Input

• Gồm số tự nhiên ~n \le 10^9~.

Output

• Số bộ số thỏa mãn.

Sample Test

Input:

3

Output:

7

Kosuzu Motoori vừa nhận được một cuốn sách lạ, bên trong là gồm các kí tự thuộc bảng chữ cái Tiếng Anh. Giá trị của một xâu là số loại kí tự xuất hiện duy nhất một lần trong xâu đó. Giá trị của cuốn sách là tổng giá trị của các xâu con liên tiếp của nội dung bên trong cuốn sách. Hãy giúp Kosuzu định giá cuốn sách này.

Input

• Gồm 1 xâu là nội dung cuốn sách. ~(|s| \le 10^5)~

Output

• In ra một số tự nhiên duy nhất là giá trị cuốn sách.

Sample Test

Input:

abcde

Output:

35

Ta định nghĩa một hàm ~f(a,n,m)~ như sau:

• ~f(a,n,m) = (a^0 + a^1 + a^2 + ... + a^n)~ mod ~m~

Cho ~t~ truy vấn, mỗi truy vấn nhập vào 3 số nguyên ~a, n, m~, hãy in ra kết quả của hàm ~f(a,n,m)~.

Giới hạn: ~1 \le a \le 10, 1 \le n,m \le 10^9~. Lưu ý, ~m~ là một số nguyên dương bất kì.

Input

• Dòng đầu gồm số nguyên dương ~t~ miêu tả số lượng truy vấn.
• ~t~ dòng sau, mỗi dòng gồm 3 số nguyên dương ~a, n, m~ miêu tả truy vấn đó.

Output

• In ra ~t~ dòng là kết quả của ~t~ truy vấn.

Sample Test

Input:

3
2 3 10000
3 3 123456
2 2 4

Output:

15
40
3

Cho bảng số ~A~ kích thước ~n*m~, các hàng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Ô giao giữa hàng ~i~ cột ~j~ là ô ~(i,j)~ và có giá trị ~a(i,j)~. Hai ô có thể di chuyển tới nhau nếu chúng chung cạnh. Một đường đi sẽ bao gồm các ô sao cho hai ô liên tiếp chung cạnh, và nó có giá trị bằng tổng giá trị các ô trên đường đi.

Cho ~q~ truy vấn, truy vấn thứ ~i~ sẽ cho bạn hai ô ~(x,y)~ và ~(u,v)~ trong bảng. Kết quả của một truy vấn chính là giá trị của đường đi có trọng số nhỏ nhất giữa hai ô đã cho. Hãy in ra kết quả của từng truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~, ~(1 \le n \le 7; 1 \le m \le 5000)~.
• Tiếp theo là ~n~ dòng, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bảng ~A~ ~n*m~, ~(0 \le a(i,j) \le 10^5)~ .
• Dòng tiếp theo là số nguyên dương ~q~, ~(q \le 30000)~.
• Ở ~q~ dòng tiếp theo mỗi dòng miêu tả một truy vấn, truy vấn thứ ~i~ có dạng ~x_i, y_i, u_i, v_i~ miêu tả ô ~(x_i,y_i)~ và ~(u_i,v_i)~. (Các ô đều nằm trong bảng).

Output

• In ra ~q~ dòng là kết quả của ~q~ truy vấn.

Sample Test

Input:

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

Output:

5
9