Winter is the coolest season of the year, but not many people like it (boring people), so you want to throw a big party for the season opening. This party is called “Winter Is Coming” or “WIC”. However to throw a big party you need some things, and this things needs to be purchased before Winter arrives to town, to this you need to walk from one point to another to buy things at the store, however some stores will not have the party articles you want, so you will need to keep looking. You are so silly that you are asking yourself to make a program that calculates the maximum amount of things you can buy before winter is finally here, to simplify the task we are going to assume some things.

1. You always start from coordinates 0, 0.
2. You will always move to the closest actual coordinate.
3. There is no need to go back home to throw the party, it can be done anywhere.
4. Each move has cost 1 in time.
5. Some stores are attached to other ones, that means their X, Y are the same, but their items are different, moving to this same place costs 1 unit of time too.

Input

An integer T specifying the number of test cases, then T test cases will follow. The first line for each test case holds an integer N that is the number of available coordinates, then N lines will follow containing position X and Y of the stores and an integer K that is the number of items you want from this specific store. Finally, an integer W specifying the time when Winter will come to town.

Output

You need to output a string “Scenario #i: “ where i is the test case you are analyzing (starting at 1) and the result, that specifies the maximum amount of things you can buy before Winter comes to town.

Example

Input:
2
5
1 2 3
2 2 0
5 5 2
3 2 0
3 3 0
3
2
1 2 0
2 2 8
1

Output:
Scenario #1: 3
Scenario #2: 0

Constraints

Subtask 1 (40%):

• 1 <= N <= 100
• 1 <= K <= 10
• 0 <= X, Y <= 100
• 1 <= W <= 100

Subtask 2 (60%):

• 1 <= N <= 1,000
• 1 <= K <= 10
• 0 <= X, Y <= 1,000
• 1 <= W <= 2,500