Prime Generator

Nguồn: https://www.codechef.com

Shridhar wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers.

Input

The first line contains t, the number of test cases (less then or equal to 10). Followed by t lines which contain two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line. Separate the answers for each test case by an empty line.

Example

Input:

2

1 10

3 5

Output:

2

3

5

7

3

5

Bytelandian gold coins

Nguồn: https://www.codechef.com

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?

Input

The input will contain several test cases (not more than 10). Each testcase is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your coin.

Output

For each test case output a single line, containing the maximum amount of American dollars you can make.

Example

Input:

12

2

Output:

13

2

You can change 12 into 6, 4 and 3, and then change these into $6+$4+$3 = $13. If you try changing the coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later you can get no more than $1 out of them. It is better just to change the 2 coin directly into $2

Chef Shifu and Celebration

Nguồn: https://www.codechef.com/

Chef Shifu wanted to celebrate the success of his new restaurant with all his employees. He was willing to host a party and he had decided the location of the party as well. However, Chef Shifu was a shy person and wanted to communicate with the least possible employees to inform them about the party, and that these employees could inform their friends.
Note that an employee could only inform his/her immediate friends about the party, not his/her friends’ friends.
Chef Shifu has a list of all the friendships among his employees. Help him find the minimum number of employees he should inform, so that every employee knows about the celebration party.

Input

First line contains a single integer T - the total number of testcases.

T testcases follow. For each testcase:

The first line contains 2 space-separated integers N and M - the total number of employees working under Chef Shifu and the number of friendship relations.

M lines follow - each line contains 2 space-separated integers u and v, indicating that employee u is a friend of employee v and vice-versa.

The employees are numbered from 1 to N, and each employee is assigned a distinct integer.

Output

For each testcase, print the minimum number of employees to be informed on a new line.

Constraints

Subtask 1: 5 points

1 ≤ T ≤ 5

1 ≤ N ≤ 4

0 ≤ M ≤ N*(N-1)/2

Subtask 2: 35 points

1 ≤ T ≤ 5

1 ≤ N ≤ 15

0 ≤ M ≤ N*(N-1)/2

Subtask 3: 60 points

1 ≤ T ≤ 5

1 ≤ N ≤ 20

0 ≤ M ≤ N*(N-1)/2

Example

Input

2

3 3

1 2

2 3

1 3

4 3

1 2

2 3

3 4

Output

1

2

Explanation

In testcase 1, since every employee is a friend of every other employee, we just need to select 1 employee.

In testcase 2, selecting employees 2 and 4 would ensure that all 4 employees are represented.

Similarly, selecting employees 1 and 3 would also ensure that all 4 employees are selected.

In both cases, we must select 2 employees in the best case.

DỤNG CỤ SAN BẰNG

Nguồn: https://www.codechef.com

Nam tạo bản đồ cho một trò chơi chiến thuật thời gian thực. Trong trò chơi này, bản đồ là một hình chữ nhật 2D với kích thước là ​N× M ô. Ban đầu, ô ở hàng ​i cột ​j có độ cao là ​H​_i,j. Độ cao luôn là số nguyên.

Trước khi tạo bản đồ, Nam muốn tất cả các ô có chiều cao như nhau. Nhưng anh ta chỉ có thể thay đổi chiều cao bằng cách dùng dụng cụ ​san bằng​. Dụng cụ san bằng có dạng hình chữ nhật với kích thước ​X × Y​, và khi sử dụng, nó thay thế chiều cao của tất cả những ô bị ảnh hưởng thành ​phần tử trung vị​. Ví dụ lưới ​5× 9​ có chiều cao:

9 8 8 8 7 7 7 8 7

1 1 1 4 4 5 2 4 4

2 3 1 2 1 2 1 1 9

3 2 8 8 9 9 7 7 7

7 7 7 7 7 7 8 8 8

Giả sử dụng cụ san bằng có kích thước ​3×7​,và chúng ta áp dụng nó vào vùng ​3×7 ở giữa. Phần tử trung vị trong vùng đó là ​3​, nên sau khi áp dụng lưới sẽ trở thành

9 8 8 8 7 7 7 8 7

1 3 3 3 3 3 3 3 4

2 3 3 3 3 3 3 3 9

3 3 3 3 3 3 3 3 7

7 7 7 7 7 7 8 8 8

Chú ý rằng ​X​ và Y ​là số lẻ, nên chỉ có một số nguyên là phần tử trung vị.

Nam muốn dùng dụng cụ san bằng đó nhiều lần để độ cao tất cả các ô đều như nhau. Hơn nữa, anh ta cũng muốn biết độ cao cuối cùng lớn nhất có thể. Độ cao lớn nhất có thể anh ta có thể đạt được là bao nhiêu ?

Ngoài ra, bạn có ​Q ​truy vấn, các truy vấn có có cặp X ​và Y ​khác nhau.

Dữ liệu vào:

·         Dòng đầu tiên chứa 3 số nguyên ​N​, ​M​, ​Q​.

·         N dòng tiếp theo thể hiện các độ cao. Mỗi dòng chứa ​M số nguyên. Giá trị thứ ​j ở dòng thứ ​i là ​H​_i,j.​

·         Q ​dòng tiếp theo là các truy vấn. Dòng thứ ​j chứa 2 số nguyên ​X​_j và ​Y_j​.

Dữ liệu ra:

Với mỗi truy vấn, in ra một dòng, chiều cao chung lớn nhất Nam có thể đạt được nếu dùng dụng cụ san bằng kích thước ​X​_j× Y_j​.

Ràng buộc:

● 3​≤​N​,​M​≤​1000

● 1​≤​Q​≤​25

● 0​≤​H_i,j ​≤ ​10​⁷

● 3​≤​X≤ ​N

●   3​≤Y​≤ ​M

●   Y_j và X_j ​là số lẻ.

Ví dụ:

EQUALIZE.INP	EQUALIZE.OUT
3 7 3 8 5 5 5 8 6 8 8 9 5 5 5 9 8 8 6 8 5 5 5 8 3 3 3 5 3 7	8 5 6

Giải thích:

Trong truy vấn đầu tiên, Nam có thể kết thúc với độ cao bằng 8 bằng việc san bằng vùng ​3× 3 bên trái nhất:

8 8 8 5 8 6 8

8 8 8 5 5 9 8

8 8 8 5 5 5 8

Sau đó là ​vùng ​3 × 3​ bên phải nhất:

8 8 8 5 8 8 8

8 8 8 5 8 8 8

8 8 8 5 8 8 8

Kết thúc bằng ​vùng ​3× 3​ ở trung tâm:

8 8 8 8 8 8 8

8 8 8 8 8 8 8

8 8 8 8 8 8 8

Có thể thấy rằng đây là độ cao lớn nhất có thể đạt được.

Test Solotion

Kitchen Timetable

Nguồn: https://www.codechef.com

Có N học sinh sống trong ký túc xá trường đại học Berland State. Mỗi bạn học sinh đôi khi muốn sử dụng bếp nên ban quản lý ký túc xá đưa ra thời gian biểu cho việc sử dụng bếp để tránh xung đột:

·       Học sinh đầu tiên bắt đầu sử dụng bếp vào thời điểm 0 và thời điểm nấu xong không được quá A₁.

·       Học sinh thứ hai bắt đầu sử dụng bếp vào thời điểm A₁ và thời điểm nấu xong không được quá A₂.

·       Cứ tiếp tục như vậy

·       Học sinh thứ N bắt đầu sử dụng bếp vào thời điểm A_N-1 và thời điểm nấu xong không được quá A_N.

Ngày nghỉ lễ ở Berland đang đến gần, nên hôm nay N học sinh đều muốn nấu bánh. Học sinh thứ i cần B_i đơn vị thời gian để nấu.

Tất cả học sinh biết rằng có thể không phải tất cả bọn họ đều nấu được mọi thứ mình muốn. Có bao nhiêu học sinh có thể nấu mà không vi phạm thời gian biểu?

Dữ liệu vào:

·       Dòng đầu tiên của input chứa số nguyên T là số lượng test. Các test được miêu tả như sau.

·       Dòng đầu tiên của mỗi test chứa một số nguyên N thể hiện số lượng học sinh.

·       Dòng thứ hai chứa N số nguyên A₁, A₂, ..., A_N thể hiện thời điểm kết thúc nấu ăn tương ứng với mỗi học sinh.

·       Dòng thứ ba chứa N số nguyên B₁, B₂, ..., B_N thể hiện thời gian cần cho mỗi học sinh nấu ăn.

Dữ liệu ra:

·       Với mỗi test, in ra một dòng chứa số lượng học sinh có thể hoàn thành việc nấu ăn.

Ràng buộc:

·       1 ≤ T ≤ 10

·       1 ≤ N ≤ 10⁴

·       0 < A₁ < A₁ < ... < A_N < 10⁹

·       1 ≤ B_i ≤ 10⁹

Ví dụ:

Input

2

3

1 10 15

1 10 3

3

10 20 30

15 5 20

Output:

    2

    1

Giải thích:

Ví dụ 1. Học sinh đầu có 1 đơn vị thời gian bắt đầu từ thời điểm 0, có đủ thời gian để nấu. Học sinh thứ hai có 9 đơn vị thời gian, nhưng lại muốn nấu trong 10 đơn vị thời gian nên không đủ thời gian. Học thứ thứ ba có 5 đơn vị thời gian và đủ thời gian bởi chỉ cần 3 đơn vị thời gian để nấu.

Ví dụ 2. Mỗi học sinh có 10 đơn vị thời gian, nhưng chỉ có duy nhất học sinh thứ hai đủ thời gian