Cho một số nguyên dương ~n~ (~n \ge 3~). Tìm số nguyên dương ~m~ (~1 \le m < n - 1~) để tổng ~GCD(m, n) + m~ đạt giá trị lớn nhất. Với ~GCD(m, n)~ là ước chung lớn nhất của 2 số ~m~ và ~n~. Nếu có nhiều số ~m~ thỏa mãn thì đưa ra số ~m~ lớn nhất.

Yêu cầu: Tìm số nguyên dương ~m~ thỏa mãn điều kiện trên.

Input

• Dòng duy nhất chứa số nguyên dương ~n~ (~n \le 10^{14}~).

Output

• Ghi ra số nguyên dương ~m~ tìm được.

Sample Input 1

15

Sample Output 1

12

Hệ thống máy quét để nhận dạng các số của một ngân hàng hiện đã bị hacker xâm nhập và làm cho chúng không thể nhận dạng được một số chữ số. Tạm gọi những chữ số mà máy quét không nhận dạng được là chữ số bị hỏng. Máy quét sẽ không nhận dạng được các số có chứa ít nhất một chữ số bị hỏng.

Ví dụ: Có 3 chữ số bị hỏng: 0, 1, 3 thì máy quét sẽ không nhận dạng được các số: 1, 3, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 30,...

Để đánh giá khả năng làm việc của máy quét, đội kiểm định đưa ra yêu cầu: biết các chữ số bị hỏng và một số nguyên dương ~n~ cho trước, họ cần biết có bao nhiêu số nguyên dương không vượt quá ~n~ mà máy quét vẫn có thể nhận dạng được.

Yêu cầu: Hãy giúp đội kiểm định tìm số lượng số nguyên dương không vượt quá ~n~ mà máy quét vẫn nhận dạng được.

Input

• Dòng 1: gồm một số nguyên dương ~n~ (~n \le 10^7~).
• Dòng 2: gồm một xâu kí tự là các chữ số bị hỏng (độ dài xâu không vượt quá 10). Các chữ số bị hỏng được viết liền tiếp không có dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số lượng các số nguyên dương không vượt quá ~n~ mà máy quét có thể nhận dạng được.

Sample Input 1

30
310

Sample Output 1

14

Sample Input 2

100000
01256789

Sample Output 2

62

Tại giờ sinh hoạt cuối năm học, cô giáo tổ chức cho các bạn học sinh chơi trò chơi. Trên bảng, có vẽ sẵn một hình chữ nhật kích thước ~1 \times n~ được chia thành ~n~ ô vuông đơn vị. Mỗi ô vuông có ghi một số nguyên dương.

Cô đưa ra một số nguyên ~m~ và yêu cầu các bạn học sinh trong lớp tìm cách tạo ra một khung hình chữ nhật kích thước ~1 \times k~ đặt lên bảng sao cho khi trượt lần lượt khung hình chữ nhật này từ trái qua phải, tổng các số trong dãy số lọt vào khung hình không được nhỏ hơn giá trị ~m~ đã cho.

Bạn nào đưa ra được khung hình kích thước ~1 \times k~ với ~k~ nhỏ nhất thỏa mãn các yêu cầu của cô giáo sẽ là người được nhận quà.

Yêu cầu: Hãy giúp cô giáo tìm đáp số để xác định được sớm nhất học sinh làm đúng yêu cầu của cô.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~ (~1 \le n \le 10^6, 1 \le m \le 10^9~).
• Dòng tiếp theo chứa lần lượt các số ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~) lần lượt là các số được viết trên các ô vuông trên bảng.
• Dữ liệu vào đảm bảo tổng của cả dãy không nhỏ hơn ~m~.

Output

• Ghi ra một số nguyên duy nhất là độ dài nhỏ nhất của khung hình mà các bạn học sinh cần tìm.

Sample Input 1

6 10
3 5 6 4 5 1

Sample Output 1

3

Cho số tự nhiên ~a~, hãy tìm số tự nhiên ~x~ thỏa mãn hai điều kiện:

• ~x \le a~.
• Biểu diễn thập phân của ~x~ gồm các chữ số theo thứ tự tăng nghiêm ngặt từ trái qua phải (từ hàng cao nhất tới hàng đơn vị). Nếu biểu diễn thập phân của ~x~ chỉ có một chữ số thì ~x~ cũng được coi là thỏa mãn điều kiện này.

Yêu cầu: Tìm số tự nhiên ~x~ lớn nhất thỏa mãn các điều kiện trên.

Input

• Dòng 1: Chứa số nguyên dương ~T \le 10^6~ là số test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số tự nhiên ~a~ ứng với một test (~0 \le a \le 10^9~).

Output

• Ghi ra ~T~ dòng, mỗi dòng ghi kết quả là số ~x~ tìm được với test tương ứng.

Sample Input 1

8
0
11
1000
5678
3498
135246
345341
123456788

Sample Output 1

0
9
789
5678
3489
134789
256789
23456789