Một Olympic mới sắp được tổ chức và thầy Thư cần lập 1 đội tuyển để tham gia thi kì thi này. Đề bài sẽ bao gồm n bài đồ thi và m bài quy hoạch động. Các học trò của thầy Thư đều rất giỏi. Nếu em nào biết giải bài đồ thị thì sẽ luôn hoàn thành trong p phút. Nếu em nào biết giải bài quy hoạch động thì sẽ luôn hoàn thành trong q phút.

    Thầy có một sinh viên rất xuất sắc là Trân – người có thể giải cả bài đồ thị và bài quy hoạch động. Các sinh viên còn lại chỉ biết giải bài đồ thị hoặc bài quy hoạch động.

    Kì thi sẽ diễn ra trong k phút, hỏi thầy Thư cần cử đi ít nhất bao nhiêu sinh viên để đảm bảo cả n + m bài đều được giải. Biết rằng mỗi sinh viên có thể giải nhiều bài nhưng không hai sinh viên nào được giải chung một bài.

Dữ liệu input:

Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 1000) là số lượng test. Sau đó là t test.

Mỗi test gồm một dòng duy nhất chứa năm số nguyên dương n, m, p, q và k 

(1 ≤ n, m, p, q, k ≤ 10 000; p, q ≤ k).

Kết quả: 

Với mỗi test, ghi ra một số nguyên là số sinh viên mà thầy Thư cần cử đi thi trên một dòng.

Ví dụ: