EBOXES - Empty Boxes

no tags 

N large empty boxes (assume they are of type:1) are initially placed on a table. An unknown number of boxes (type:1) are selected and in each of them K smaller boxes (type:2) are placed. Again an unknown number of type:2 boxes are selected and K boxes of type:3 are placed inside. This process is repeated T times. Now a box is assumed to be empty when it has no smaller boxes inside it. Finally after all the processes are complete let there be F empty boxes in total.

LIMITS

1< N, K, T, F <1000000

Input

First line of the input file contains the number of test cases. Then each line contains 4 integers N, K, T, F as described above.

Output

Each line should contain the total number of boxes on the table.

Example

Input:
1
11 8 2 102

Output:
115

hide comments
dkkv0000: 2019-05-13 13:37:45

https://skasturi.wordpress.com/2009/03/10/problem-solving-1/

ankkt16: 2019-02-24 07:40:47

simple maths...just observe...did it in O(1):)

abhishek_328: 2018-08-07 15:31:47

No need of T !!! Just fill level until empty box < F ,then count empty box+non empty box ... Be carefull while filling last level because it may be possible that a portion of last level is filled !!!!

starboy_jb: 2018-01-19 10:15:36

problem statement is not clear...

karthik1997: 2017-12-29 18:06:45

Just write total number of empty boxes of every type after every iteration considering unknown variables as i1,j1 etc ( unknown number of boxes as i1 of type1 and j1 for type2 etc) and summate them .
Similarly Count total number of every type of boxes after every iteration and summate them . you'll get the answer :)

utkarshsingh99: 2017-11-22 22:15:17

Just a maths problem. AC in one go

kush_pathak01: 2017-10-28 14:25:17

AC in one go!! easy one!!

piyush11696: 2017-08-14 11:13:55

Ac in one go : )

kaushalag29: 2017-05-17 20:06:36

AC in one go
independent of T as a hint...

rohit9934: 2017-05-16 10:51:24

Time Limit is 2.3 but acceptable in 0.00 sec with ease.


Added by:abhijith reddy d
Date:2009-05-07
Time limit:2.369s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET