There is a special offer in Vasya's favourite supermarket: if the customer buys a chocolate bars, he or she may take b additional bars for free. This special offer can be used any number of times.

Vasya currently has s roubles, and he wants to get as many chocolate bars for free. Each chocolate bar costs c roubles. Help Vasya to calculate the maximum possible number of chocolate bars he can get!

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of testcases.

Each of the next t lines contains four integers s, a, b, c~(1 ≤ s, a, b, c ≤ 10^9) — the number of roubles Vasya has, the number of chocolate bars you have to buy to use the special offer, the number of bars you get for free, and the cost of one bar, respectively.

Output

Print t lines. i-th line should contain the maximum possible number of chocolate bars Vasya can get in i-th test.

Example

Input

2
10 3 1 1
1000000000 1 1000000000 1


Output

13
1000000001000000000

Note

In the first test of the example Vasya can buy 9 bars, get 3 for free, buy another bar, and so he will get 13 bars.

In the second test Vasya buys 1000000000 bars and gets 1000000000000000000 for free. So he has 1000000001000000000 bars.


import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.function.Function;
import java.util.function.ToIntFunction;


public class GFG
{
    static int mod1 = (int) (1e9 + 7);

    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do
            {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }

        public int[] nextArray(int n) throws IOException
        {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = nextInt();
            }
            return a;
        }
    }

    static Set<Long> divisor(Set<Long> set0, long num0)
    {
        set0.add(1L);
        long num00=(long)(Math.sqrt(num0))+1;
        for (long i = 2; i<num00; i++)
        {
            if (num0 % i == 0)
            {
                set0.add(i);
                set0.add(num0/i);
            }
        }
        return set0;
    }
    static long primeDivisor(long num0)
    {
        HashMap<Long,Integer> hMap1=new HashMap<>();
        boolean b0=false;
        boolean b1=primeCheck(num0);
        if(b1)
        {
            hMap1.put(0L,1);
        }
        else
        {
            for (long i = 2; i * i <= num0; i++)
            {
                while (num0 % i == 0)
                {
                    if (hMap1.containsKey(i))
                    {
                        hMap1.replace(i,(hMap1.get(i)+1));
                    }
                    else
                    {
                        hMap1.put(i,1);
                    }
                    num0 = num0 / i;
                }

            }
            boolean b2=primeCheck(num0);
            if(b2 && num0!=1)
            {
                if(hMap1.containsKey(num0))
                {
                    hMap1.replace(num0,(hMap1.get(num0)+1));
                }
                else
                {
                    hMap1.put(num0,1);
                }
            }
        }

        long num00=0;
        for(long num000:hMap1.keySet())
        {
            num00+=(sum0(String.valueOf(num000))*hMap1.get(num000));
        }

        return num00;
    }

    static int sum0(String str0)
    {
        int num0000=0;
        int len0=str0.length();
        for(int i=0;i<len0;i++)
        {
            num0000+=Character.getNumericValue(str0.charAt(i));
        }
        return num0000;
    }

    static long power2(long x, long y, long p)
    {
        long res = 1;
        x = x % p;
        while (y > 0)
        {
            if ((y & 1) == 1)
            {
                BigInteger res0 = BigInteger.valueOf(res);
                res0 = res0.multiply(BigInteger.valueOf(x));
                res0 = res0.mod(BigInteger.valueOf(p));
                String str0 = res0.toString();
                res = Long.parseLong(str0);
            }
            y = y >> 1;
            BigInteger res00 = BigInteger.valueOf(x);
            res00 = res00.multiply(BigInteger.valueOf(x));
            res00 = res00.mod(BigInteger.valueOf(p));
            String ans00 = res00.toString();
            x = Long.parseLong(ans00);

        }
        return res;
    }

    static long GCD(long num0, long num00)
    {
        BigInteger big1 = BigInteger.valueOf(num0);
        BigInteger big2 = BigInteger.valueOf(num00);
        big1 = big1.gcd(big2);
        long num000 = Long.parseLong(big1.toString());
        return num000;
    }

    static boolean primeCheck(long num0)
    {
        boolean b1 = true;
        if(num0==1)
        {
            b1=false;
        }
        else
        {
            int num01 = (int) (Math.sqrt(num0)) + 1;
            me1: for (int i = 2; i < num01; i++)
            {
                if (num0 % i == 0)
                {
                    b1 = false;
                    break me1;
                }
            }
        }
        return b1;
    }

    static double getTime()
    {
        return System.nanoTime();
    }

    static int countSum1(int len0, int[] arr0, int sum0)
    {
        HashMap<Integer, Integer> map1 = new HashMap<>();

        for (int i = 0; i < len0; i++)
        {
            if (!map1.containsKey(arr0[i]))
            {
                map1.put(arr0[i], 0);
            }
            map1.put(arr0[i], map1.get(arr0[i]) + 1);
        }
        int count0 = 0;
        for (int i = 0; i < len0; i++)
        {
            if (map1.get(sum0 - arr0[i]) != null)
                count0 += map1.get(sum0 - arr0[i]);
            if (sum0 - arr0[i] == arr0[i])
                count0--;
        }
        int num7 = count0 / 2;
        return num7;
    }


/*
    static ArrayList<Long> primeDevisor(ArrayList<Long> arrLst0,long num0)
    {
        arrLst0.add(1L);
        arrLst0.add(num0);

        me1: for (long i = 2; i * i < num0+1; i++)
            {
                while (num0 % i == 0)
                {
                    if(!arrLst0.contains(i))
                    {
                        arrLst0.add(i);
                    }
                    num0 = num0 / i;
                }
            }
            boolean b2=primeCheck(num0);
            if(b2 && num0!=1)
            {
                if(!arrLst0.contains(num0))
                {
                    arrLst0.add(num0);
                }
            }
        }
        return arrLst0;
    }
*/




    public static void main(String[] args) throws IOException
    {
        //double tTime   = getTime()-(startTime);
        //out1.print(tTime/(1e9)+" ");
        Reader r = new Reader();
        //Scanner r = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        //Scanner r=new Scanner(System.in);
        OutputWriter3 out1 = new OutputWriter3(System.out);

        int cas1=r.nextInt();
        while(cas1-->0)
        {
            long num1=r.nextLong();
            long num2=r.nextLong();
            long num3=r.nextLong();
            long num5=r.nextLong();

            long num7=num2*num5;
            long num9=num1/num7;
            long num10=(num9*(num2+num3));
            num9=num1%num7;
            num10+=(num9/num5);

            out1.print(num10+"\n");

        }
        r.close();
        out1.close();
    }
}
/*class linkedList
{
    Node head;

    static class Node
    {
        int data;
        Node next;

        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    public void print()
    {
        Node ptr1 = head;
        while (ptr1 != null)
        {
            System.out.print(ptr1.data + " ");
            ptr1 = ptr1.next;
        }
    }
}
*/
class OutputWriter3
{
    BufferedWriter writer;

    public OutputWriter3(OutputStream stream)
    {
        writer = new BufferedWriter(new OutputStreamWriter(stream));
    }

    public void print(int i) throws IOException
    {
        writer.write(i + "");
    }

    public void println(int i) throws IOException
    {
        writer.write(i + "\n");
    }

    public void print(String s) throws IOException
    {
        writer.write(s + "");
    }

    public void println(String s) throws IOException
    {
        writer.write(s + "\n");
    }

    public void print(char[] c) throws IOException
    {
        writer.write(c);
    }

    public void close() throws IOException
    {
        writer.close();
    }
}