Bạn X thiết kế ra một máy đánh số thứ tự có ba chữ số, nên được giao nhiệm vụ đánh mã số lên các thiết bị của công ty. Chiếc máy đánh số từ \(001, 002, 003, \dots, 997, 998, 999\) rồi sau đó quay lại \(001, 002, 003, \dots\).

Hãy cho biết, thiết bị thứ \(n\) có mã số là bao nhiêu?

Input

Một số \(n (n \le 10^9)\) duy nhất.

Output

In ra một số duy nhất là mã số của thiết bị thứ \(n\).

Ví dụ:

Subtask

• 60% test có \(n \le 10^5\)
• 40% test còn lại có \(n \le 10^9\)

Cho một mảng \(A\) có \(n\) phần tử. Hãy tìm chênh lệch nhỏ nhất giữa hai phần tử bất kỳ của \(A\).

Input

• Dòng đầu tiên chứa một số \(n\) \((n \le 10^5)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa một số \(A_i\) \((A_i \le 10^9)\).

Output

In ra kết quả là chênh lệch nhỏ nhất giữa hai phần tử bất kỳ của \(A\).

Ví dụ:

Sample Input 1:

5
2 
4 
1 
8 
2

Sample Output 1:

0

Sample Input 2:

5
20 
9 
2 
5 
13

Sample Output 2:

3

Giới hạn

• 60% số test có \(n \le 10^3\)
• 40% còn lại có \(n \le 10^5\)

Ta định nghĩa một phép nhân giữa một chuỗi \(a\) và một số nguyên dương \(x\): \(a.x\) là một chuỗi được hình thành bằng cách sao chép \(x\) lần chuỗi \(a\).

Ví dụ: "abc".\(2\) = "abcabc", "a".\(5\) = "aaaaa".

Một chuỗi \(a\) được gọi là chia hết cho chuỗi \(b\) nếu tồn tại một số nguyên \(x\) sao cho \(b.x\) = \(a\).

Ví dụ "abababab" chia hết cho chuỗi "ab", nhưng không chia hết cho "ababab" hoặc "a".

\(LCM\) của hai chuỗi \(s\) và \(t\) là chuỗi ngắn nhất khác rỗng sao cho chuỗi \(s\) và chuỗi \(t\) chia hết cho chuỗi đó.

Bạn được cho hai chuỗi \(s\) và \(t\). Hãy tìm \(LCM(s, t)\).

Input

Dòng đầu tiên gồm 1 số nguyên \(q\) \((1\leq q \leq 2000)\) là số lượng test case.

Mỗi test case có hai dòng, chứa chuỗi \(s\) và \(t\) \((1 \leq |s|, |t| \leq 20)\). Mỗi kí tự trong mỗi là một trong hai kí tự 'a' hoặc 'b'.

Output

Mỗi test case, in ra bội chung nhỏ nhất \(LCM(s, t)\) nếu tồn tại, ngược lại in ra -1.

Input

3
baba
ba
aa
aaa
aba
ab

Output

baba
aaaaaa
-1

Phi hành đoàn trên con tàu vũ trụ Chết chóc phải hoàn thành các nhiệm vụ để vận hành và duy trì con tàu. Vì trong số họ có các imposter đang chực chờ cơ hội để tiêu diệt họ, một số người đã đi thành cặp để bảo vệ lẫn nhau. Tuy nhiên không phải cặp nào cũng đủ sức mạnh để chống trả lại bọn imposter gian ác. Tất cả các phi hành đoàn sẽ mang 1 con số báo danh trong đoạn từ \(L\) đến \(R\) và imposter nhận ra rằng, một cặp đôi \(a\) và \(b\)
là bất khả chiến bại nếu như tổng số ước của \(a\) không bao gồm \(a\) bằng \(b\) và ngược lại tổng số ước của \(b\) không bao gồm \(b\) bằng \(a\). Là 1 imposter, bạn hãy lập trình để xác định những cặp bất khả chiến bại này để loại trừ ra nhằm tiêu diệt những nhóm yếu ớt hơn.

Yêu cầu: Cho 2 số nguyên dương \(L\) và \(R (L<R)\). Hãy đếm số lượng cặp \((a,b)\) mà \(L \le (a,b) \le R\) và đó là cặp đôi bất khả chiến bại, cặp \((a,b)\) và \((b,a)\) được tính là 1.

Input

Gồm 1 dòng duy nhất 2 số nguyên dương \(L,R (L\le R \le 10^6)\)

Output

Số lượng cặp bất khả chiến bại

Ví dụ

Input:

219 285

Output:

1

Bằng cách xếp những khối lập phương lại với nhau, ta có thể tạo nên những kim tự tháp cho riêng mình.

Tháp có độ cao 3, nhìn 1 bên (Đông Tây Nam Bắc) và nhìn từ trên xuống

Vậy cần bao nhiêu khối lập phương để tạo nên một tháp lá bài có độ cao \(n\).

**Input: **

• Dòng đầu, chứa số nguyên dương \(T (T \le 10^6)\) - số lượng câu hỏi.
• \(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(n(n \le 10^9)\).

**Output: ** Gồm \(T\) dòng, mỗi dòng chứa số lượng khối lập phương tối thiểu để tạo một tháp có chiều cao \(n\) tương ứng. (lấy số dư khi chia cho \(10^9+7\))

**Example Input: **

3
1
2
3

**Example Output: **

1
10
35