Perfect Game

You are playing a video game that gives you an achievement if you clear every level consecutively without dying. You may play the levels in any order you like, and each attempt at a level either clears it or kills you. Every level has a fixed chance of killing you and a fixed duration for one attempt. Dying in a level takes exactly as long as clearing it. As soon as you die, you start again from the first level of your chosen order.

Find the order of levels that minimizes the expected time to earn the achievement.

Note: failing a level kills only your character in the game, not you. Otherwise almost nobody would go after this achievement.

The first line contains the number of test cases $T$. Then $T$ test cases follow, each of which consists of three lines.

The first line of each test case contains the number of levels $N$. The second line contains $N$ space-separated integers $L_i$. $L_i$ is the number of seconds one attempt at level $i$ lasts, and it is the same whether you clear the level or die in it. The third line contains $N$ space-separated integers $P_i$. $P_i$ is the percent chance that you die in any single attempt at level $i$.

Limits

• $1 \le T \le 100$
• $1 \le N \le 20$
• $1 \le L_i \le 100$
• $0 \le P_i < 100$

For each test case, print one line starting with Case #x: , where $x$ is the case number starting from 1. After it print $N$ space-separated integers. The $j$th integer is the index of the $j$th level you attempt, and the order must minimize the expected time to earn the achievement. Level indices run from $0$ to $N-1$.

If several orders give the same expected time, print the lexicographically least one. Between two orders, the one with the smaller index at the first position where they differ comes first lexicographically. Among many orders, the lexicographically least one is the order that is lexicographically smaller than every other order.