Tudor is sitting in math class, on his laptop. Clearly, he is not paying attention in this situation. However, he gets called on by his math teacher to do some problems. Since his math teacher did not expect much from Tudor, he only needs to do some simple addition problems. However, simple for you and I may not be simple for Tudor, so please help him!

Input Specification

The first line will contain an integer ~N~ (~1 \le N \le 100\,000~), the number of addition problems Tudor needs to do. The next ~N~ lines will each contain two space-separated integers whose absolute value is less than ~1\,000\,000\,000~, the two integers Tudor needs to add.

Output Specification

Output ~N~ lines of one integer each, the solutions to the addition problems in order.

Sample Input

2
1 1
-1 0

Sample Output

2
-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