F. Research projects
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Each year in NCD, students participate in school research projects. Each project must have a team of at least $$$1$$$ student and at most $$$6$$$ students. And each student can only participate in one project.

However, not all the students found teams to join this year. So the administration will set new projects to accommodate these students. Your job is to find out the minimum number of new projects to accommodate all these students.

Input

In the first line $$$T$$$, the number of test cases.

For each test case you will be given ($$$N$$$, $$$K$$$) the number of students in the NCD and the number of students who have projects.

$$$ 1 \le N, K \le 10^{18} $$$

Output

For each test case print the least number of the new projects.

Example
Input
4
12 7
11 4
3 1
34 4
Output
1
2
1
5