FAMWEALT - Family members

Consider a family in the form of a binary tree consisting of male and female nodes. All the left nodes will be male nodes and all the right nodes will be female nodes.

Root node will be female node. The root female initially has a wealth w which she passes on down the tree. The rules are as follows:

  1. all the males in the family pass half of their wealth to each of their children.
  2. all the female nodes pass only half of their wealth to both their children collectively, but the male child suddenly converts it to twice the wealth received.

The members are numbered from 1 to n in the row-wise order. i.e., root will be 1, the two children will be 2 and 3 and so on.

Given wealth W of xth node, you need to find the wealth of yth node.

Input

First line consists of t, the number of test cases (1 ≤ t ≤ 20).

Each of t lines consists of three integer values x, y and W (1 ≤ x, y ≤ 106 and 1 ≤ W ≤ 1000).

Output

For each input test case, print the wealth of yth node in a single line (rounded off to six decimal digits.)

Example

Input:
2
11 3 1
4 6 4

Output:
4.000000
2.000000

Added by:Pandian
Date:2013-12-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2014-03-06 23:19:06 innovolt
weak constraint........AC
2014-03-01 18:29:58 vikrant
wow ac in first attempt :D
2014-02-15 11:04:01 Abhishek Gupta
getting wa again & again...any tricky part that one can miss...plz help
i have posted my code at forum>>
[url]
https://www.spoj.com/forum/viewtopic.php?f=3&t=21787&sid=45d4d66470fa23e9ac73ba49ac68702f
[/url]

Last edit: 2014-02-15 11:13:06
2014-01-22 15:49:22 aqfaridi
@Pandian : You should increase number of test cases to 10^5
2014-01-21 17:50:18 BA_AK
Too Easy!
Caution: For some algorithms, u need to use long long.

Century on Spoj !! Yeah!
2013-12-31 19:45:45 pushkar nagar
any tricky test cases....help
wa+wa+wa+wa+wa+wa=i want to do this question anyhow...

Last edit: 2013-12-31 20:18:02
2013-12-30 20:00:35 ήάέέϻ Ÿ
getting WA again and again.. dnt know wats going wrong :(
2013-12-27 10:23:40 Saimadhav Heblikar
nice problem.
2013-12-26 10:21:25 Chandan Singh
Nice problem @Pandian :)
2013-12-26 10:01:42 Ankit Kumar
Nice problem :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.