Tudor đang ngồi trong giờ toán với chiếc máy tính xách tay của mình. Rõ ràng là anh ấy đang không chú ý vào bài giảng. Tuy nhiên, giáo viên toán đã gọi Tudor lên để giải một số bài tập. Vì giáo viên không kỳ vọng quá nhiều, Tudor chỉ cần thực hiện một số phép cộng đơn giản. Hãy giúp Tudor giải quyết những bài toán này!

Input

Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^5~), là số lượng phép cộng Tudor cần thực hiện. ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách, có giá trị tuyệt đối nhỏ hơn ~10^9~.

Output

Ghi ra ~N~ dòng, mỗi dòng là một số nguyên là kết quả của phép cộng tương ứng theo thứ tự.

Sample Input 1

2
1 1
-1 0

Sample Output 1

2
-1

Giải thích

• Phép tính thứ nhất: ~1 + 1 = 2~.
• Phép tính thứ hai: ~-1 + 0 = -1~.

Xét xâu nhị phân, tức là xâu chỉ chứa các ký tự trong tập ~{0, 1}~. Gọi ~k~ là số lượng xâu nhị phân độ dài ~n~ ~(1 \le n \le 10^4)~ chứa xâu ~S~ (độ dài không quá ~100~) như một xâu con (các ký tự liên tiếp) đúng một lần.

Yêu cầu: Hãy tính phần dư của kết quả chia ~k~ cho ~10^9+7~.

Input

• Dòng thứ nhất chứa số nguyên ~n~,
• Dòng thứ hai chứa xâu ~S~.

Output

• Một số nguyên – kết quả tìm được.

Sample Input

4
01

Sample Output

10

Chính phủ quốc đảo Oceani quyết định xây dựng ~m~ chiếc cầu nối ~n~ đảo của mình, tạo một mạng lưới giao thông đường bộ cho phép đi từ dảo bất kỳ tới đảo khác bằng đường bộ (trực tiếp hoặc qua một số đảo trung gian). Mỗi cây cầu sẽ nối ~2~ đảo khác nhau và cho phép đi lại hai chiều. Các đảo được đánh số từ ~0~ đến ~n-1~. Bị hạn chế bởi kinh phí và nguồn nhân lực, người ta quyết định sẽ xây dựng lần lượt từng chiếc cầu một và lên kế hoạch xác định cầu và trình tự xây. Mỗi cây cầu được xác định bởi cặp đảo ~u~, ~v~ mà nó nối. Trong quá trình thực hiện kế hoạch có thể đến một lúc nào đó từ một đảo đã có thể đi đến bất kỳ đảo khác bằng đường bộ.

Ví dụ, ở Oceani có ~4~ đảo và người ta quyết định xây dựng ~5~ cầu theo trình tự lần lượt là ~0 – 1, 0 – 2, 1 – 2, 2 – 3, 3 – 0~. Tuy vậy, không cần chờ đợi đến khi hoàn thành kế hoạch xây cầu, sau khi cầu thứ ~4~ được xây xong tất cả các đảo đã được nối liền bằng đường bộ.

Yêu cầu: Cho ~n~, ~m~ và các cây cầu dự kiến xây. Thông tin về các cây cầu đưa ra theo đúng trình tự xây dựng. Hãy xác định số cầu tối thiểu cần xây theo kế hoạch để từ một đảo đã có thể đi đến bất kỳ đảo khác bằng đường bộ.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n \le 10^6,\ 1 \le m \le 5*10^6)~,
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ~2~ số nguyên ~u~ và ~v~ xác định cây cầu thứ ~i~ cần xây.

Output

• Một số nguyên – kết quả tìm được.

Sample Input

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

Sample Output

4

Dãy số nguyên dương tăng dần, trong đó ước nguyên tố của mỗi số không quá ~5~ được gọi là dãy Hamming. Như vậy, ~10 = 2\times5~ sẽ là một số trong dãy Hamming, còn ~26 = 2\times13~ – không thuộc dãy Hamming.

Phần đầu của dãy Hamming là ~1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \dots~

Yêu cầu: Cho số nguyên ~x~ ~(1 \le x \le 10^{18})~. Hãy xác định số thứ tự của ~x~ trong dãy Hamming.

Input

• Dòng đầu tiên chứa số nguyên ~t~ – số lượng tests ~(1 \le t \le 10^5)~,
• Mỗi dòng tiếp theo chứa một số nguyên ~x~.

Output

• Kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên hoặc thông báo Not in sequence.

Sample Input

11
1
2
6
7
8
9
10
11
12
13
14

Sample Output

1
2
6
Not in sequence
7
8
9
Not in sequence
10
Not in sequence
Not in sequence