题目描述

草帽海贼团的路飞船长驾着万里阳光号，环游大半个地球，历经艰险，终于找到了前任海贼王罗杰的宝藏盒。可惜宝盒异常坚固，怎么都打不开，上面只有四个每隔一分钟变化一次的整数，还有一个用来输入密码的锁。路飞尝试了很多密码，但都不对。不过一天夜里，卡吕普索女神托梦给他，告诉他：盒子的密码是不断变化的，如果设某一时间盒子上的四个整数，从左到右分别为l,h,a,b，则此时盒子的密码为满足以下三个条件的最小的整数 x：

1. l <= x 且 x <= h
2. a mod x = 0
3. x mod b = 0

路飞虽然勇敢，也很聪明，但他可不是一个优秀的算法专家，现在请你来帮他解决这个问题。

输入格式

首先是一个整数 t，表示有 t 组测试数据。（t <= 1000） 每组有四个整数 l, h, a, b ( 1 <= l, h, a, b <= 100000 ), a ∉ [ l , h ]。

输出格式

对于每组数据输出一行 "Case #c: x"，c 表示第几组测试数据（从1开始）， x 为结果，若不存在满足这些条件的整数，则结果为 -1。

样例数据

input

2
5 10 18 3
19 21 18 3

output

Case #1: 6 
Case #2: -1