005 - 浪費

時間制限 1 秒 / メモリ制限 256 MB / 得点 400 / x 14 /


TLE
1sec
MLE
256MB
得点
400

問題

ノイズの大きいイヤホンを買ってしまった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
日数 1 2 3 4 5
浪費額 30 100 100 30 100
貯金 330 300 200 100 0

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


入力例2

3
512 128 256
314159 27182 235711
919 1 10000000

出力例2

2
2
113777