在冬马曜子工作室的安排下，和纱会在维也纳休养$a$天，然后去日本开$b-a$天音乐会，并以$b$天为一周期不断循环。而根据Knight Records的工作安排，雪菜会去外地出差$c$天，然后休息$d-c$天，并以$d$天为以一周期不断循环。如果雪菜处在休息时间，那么她一定会去和纱在当天的音乐会（即使她前一天也去过了）。春希想知道在前$n$天中，雪菜一共去了几天音乐会。
第一行一个整数$T(1 \le T \le 20000)$，代表数据组数。
之后每组数据一行，包含$5$个整数$a,b,c,d,n(1 \le a < b \le 10^9, 1 \le c < d \le 10^9, 1 \le n \le bd)$。
对于每组数据输出一行一个整数，代表雪菜去音乐会的天数。
4 5 7 2 3 14 6 7 5 7 31 2 3 13 14 40 2 4 5 9 36
1 4 0 8
Comet OJ