Năm ~404~ BC, vùng đất Westeros đang xôn xao vì một bài toán rất lạ được đưa ra từ một kẻ ẩn danh tới từ Essos. Khắp bảy phụ quốc, các lãnh chúa liên tục tìm người để giải quyết bài toán nhưng đều thất bại. Bài toán được lan truyền tới Oldtown và khiến các Maester ở Citadel cũng phải đau đầu. Hãy giúp các học sĩ giải quyết bài toán này nhé:

Số đẹp được định nghĩa là một số nguyên dương và chia hết cho một trong ba số: ~3~, ~5~, hoặc ~7~.

Ví dụ về dãy các số đẹp: ~3, 5, 6, 7, 9, 10, 12, 14, 15, 18,...~

Hãy tìm số đẹp thứ ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~k~.

Output

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

Sample Test

Input 1

2

Output 1

5

Input 2

10

Output 2

18

Giới hạn:

• Subtask 1 (50% số điểm): ~k \le 10^6~
• Subtask 2 (50% số điểm): ~k \le 10^9~

Với một số nguyên dương ~n~, ta gọi nó là số cô đơn nếu ~n~ chỉ có một ước trong đoạn ~[\lceil \frac{n}{10} \rceil,n]~, tức là chỉ tồn tại một số ~x~ thỏa mãn:

• ~\lceil \frac{n}{10} \rceil\le x\le n~

• ~n~ chia hết cho ~x~

Trong đó, ~\lceil x \rceil~ ký hiệu cho số nguyên bé nhất không nhỏ hơn ~x~.

Người ta đem các số cô đơn sắp xếp lại theo thứ tự tăng dần về giá trị: ~1, 11, 13, 17, 19, 23, \ldots~

Yêu cầu: Cho hai số nguyên ~v, k~. Bạn hãy trả lời hai câu hỏi:

• ~v~ là số cô đơn thứ bao nhiêu trong dãy trên?

• Số cô đơn thứ ~k~ trong dãy có giá trị là bao nhiêu?

Dữ liệu đảm bảo ~v~ là số cô đơn giống bạn.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(1 \le T \le 10^4)~ là số bộ dữ liệu;

• ~T~ dòng tiếp theo, mỗi dòng bao gồm:

  • Hai số nguyên dương ~v, k~ ~(v, k \le 10^{18})~

Output

• In ra ~T~ dòng, mỗi dòng in ra hai số nguyên là câu trả lời cho bộ dữ liệu tương ứng.

Scoring

Sample Input 1

2
13 5
19 3

Sample Output 1

3 19
5 13

Sample Input 2

2
1 1
289 10062006

Sample Output 2

1 1
67 44021273

Notes

Dãy các số cô đơn sắp xếp lại theo thứ tự tăng dần là: ~[1, 11, 13, 17, 19, 23, \ldots]~.

Ở test ví dụ thứ nhất, ~13~ là số cô đơn thứ ba và số cô đơn thứ năm trong dãy là ~19~.

Cho số nguyên dương ~n~ và ~q~ truy vấn, truy vấn thứ ~i~ bạn nhận được hai số nguyên dương ~l_i~ và ~r_i~.

Với mỗi truy vấn, nhiệm vụ của bạn là đếm số số nguyên dương ~x \in [l_i,r_i]~ sao cho ~(x,n) = 1~, nói cách khác là ~x~ nguyên tố cùng nhau với ~n~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1 \le n \le 10^{12}; 1 \le q \le 10^4)~.
• ~q~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~l_i~ và ~r_i~ miêu tả truy vấn thứ ~i~ ~(1 \le l_i \le r_i \le 10^{16})~.

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Sample Test

Input:

6 3
2 7
3 5
6 9

Output:

2
1
1

Xét dãy vô hạn các số tự nhiên liên tiếp bắt đầu từ ~1~: ~1, 2, 3,...~ và ~n~ số nguyên dương ~a_1, a_2, ...,a_n~. Trên dãy vô hạn các số tự nhiên này, tiến hành xóa hết các số chia hết cho ~a_1~, sau đó xóa hết các số chia hết cho ~a_2~ mà chưa được xóa,..., cuối cùng xóa hết các số chia hết cho ~a_n~ mà chưa được xóa. Đánh số các số chưa được xóa bắt đầu từ ~1~, người ta muốn biết số được đánh số thứ ~k~ là số nào?

Yêu cầu: Cho dãy số ~a_1, a_2, ..., a_n~ và ~k~, hãy tìm số tự nhiên được đánh số thứ k trên dãy sau khi xóa.

Input

• Dòng đầu chứa số nguyên ~T~ là số bộ dữ liệu;
• ~T~ nhóm dòng sau, mỗi nhóm có dạng:
  • Dòng đầu của nhóm chứa hai số nguyên dương ~n~ và ~k~ ~(1 ≤ k ≤ 10^{15})~;
  • Dòng thứ hai của nhóm chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 < a_i ≤ 10^{15})~.

Output

• Gồm ~T~ dòng, mỗi dòng chứa một số tự nhiên là kết quả tương ứng của bộ test trong dữ liệu vào.

Subtasks

• Subtask 1: ~n = 1~.
• Subtask 2: ~n = 2~.
• Subtask 3: ~n \le 10~.

Sample Test

Input:

2
1 5
2
2 2
2 3

Output:

9
5

Đếm số cách chia ~n~ cái kẹo cho ~k~ người sao cho số kẹo của mỗi người nhận được đều thuộc đoạn ~[0,n]~. Hai cách chia kẹo được coi là khác nhau nếu tồn tại một người nhận được số kẹo khác nhau trong hai cách.

Nói cách khác, đếm số nghiệm nguyên của phương trình: ~x_1 + x_2 + ... + x_k = n~, sao cho ~\forall i \in [1,n]: 0 \le x_i \le n~.

Input

• Gồm hai số nguyên dương: ~n~ ~k~

Constraint

• ~1 \le k \le n \le 10^6~

Subtask

• Subtask ~1~ ~(30\%)~: ~1 \le n \le 10~.
• Subtask ~2~ ~(30\%)~: ~k \le n \le 1000~
• Subtask ~3~ ~(40\%)~: ~k \le n \le 10^6~

Output

• In ra kết quả bài toán sau khi chia lấy dư cho ~10^9+7~.

Sample Input 1:

6 3

Sample Output 1:

28

Đếm số cách chia ~n~ cái kẹo cho ~k~ người sao cho số kẹo của mỗi người nhận được đều thuộc đoạn ~[L,H]~. Hai cách chia kẹo được coi là khác nhau nếu tồn tại một người nhận được số kẹo khác nhau trong hai cách.

Nói cách khác, đếm số nghiệm nguyên của phương trình: ~x_1 + x_2 + ... + x_k = n~, sao cho ~\forall i \in [1,n]: L \le x_i \le H~.

Input

• Gồm bốn số nguyên dương: ~n~ ~k~ ~L~ ~H~ ~(0 \le L \le H \le n)~

Constraint

• ~1 \le k \le n \le 10^6~

Subtask

• Subtask ~1~ ~(30\%)~: ~1 \le n \le 10~.
• Subtask ~2~ ~(30\%)~: ~k \le n \le 1000~
• Subtask ~3~ ~(40\%)~: ~k \le n \le 10^6~

Output

• In ra kết quả bài toán sau khi chia lấy dư cho ~10^9+7~.

Sample Input 1:

6 3 0 6 

Sample Output 1:

28

Sample Input 2:

6 4 0 2 

Sample Output 2:

10

Cho bốn số nguyên dương ~n,k,a,b~. Hãy đếm số dãy số nguyên dương ~x_1,x_2,...,x_n~ sao cho:

• Với mọi ~1 \le i \le n~, ~a \le x_i \le b~.
• Bội số chung nhỏ nhất của các số ~x_1,x_2,...,x_n~ chia hết cho ~k~.

Do số lượng dãy có thể rất lớn, hãy in ra nó sau khi lấy modulo cho ~998244353~.

Input

• Gồm một dòng duy nhất chứa bốn số nguyên ~n,k,a~ và ~b~. ~(1 \le n \le 227, 1 \le k \le 10^{14}, 1 \le a \le b \le 10^{14})~.

Output

• In ra kết quả cua bài toán sau khi lấy modulo cho ~998244353~.

Subtask

• Subtask ~1~ ~(10\%)~: ~k = 1~
• Subtask ~2~ ~(10\%)~: ~n \le 5, b \le 30~ và ~k \le 30~
• Subtask ~3~ ~(20\%)~: ~n \le 5~ và ~b-a \le 30~
• Subtask ~4~ ~(20\%)~: ~k~ là số nguyên tố
• Subtask ~5~ ~(20\%)~: ~b \le 10^7~ và ~k \le 10^7~
• Subtask ~6~ ~(20\%)~: Không có ràng buộc gì thêm.

Sample Input 1

2 6 10 14

Sample Output 1

9

Sample Input 1

3 5 7 9

Sample Output 1

0