005 - 浪費

問題

ノイズの大きいイヤホンを買ってしまったYTA。彼は憤慨していっそのこと貯金をなくしてしまおうと考えました。
YTAの現在の貯金は $S$ 円です。
1日で貯金を使い切るのはつまらないので、以下のルールにしたがって今日から毎日お金を浪費することにしました。

• 浪費を始めてからの経過日数を $i$ としたとき、
• $i$ が素数になる日は、$A$ 円ちょうど浪費する。
• そうでない日は、$B$ 円ちょうど浪費する。
• 残りの貯金が浪費する金額よりも少ない場合は、貯金は使い切って $0$ 円になる。

このルールで浪費したとき、YTAの貯金が底を尽きるのは何日目なのか求めてください。
ただし、浪費を始めた日を $1$ 日目とします。

入出力形式

入力

入力は複数のデータセットからなる。
1行目にデータセット数 $N$ が入力され、続く $N$ 行にデータセットが一行ずつ与えられる。

N
data1
data2
  :
dataN

各データセットは、次の形式で入力される。

A B S

出力

貯金が初めて $0$ 円になるのは何日目かを1行に出力してください。

制約

• $1 \le N \le 10^{4}$
• $1 \le A, B \le 10^{7}$
• $1 \le S \le 10^{7}$

部分点

• $N \le 100$ かつ $S \le 10^{5}$ を満たすテストケースに正解すると、配点の 20% が与えられる。

入出力例

入力例

1
100 30 360

出力例1

5

上の表のようになる。2, 3, 5日目は日数が素数なので $100$ 円浪費する。

入力例2

3
512 128 256
314159 27182 235711
919 1 10000000

出力例2

2
2
113777