Vova is playing a computer game. There are in total n turns in the game and Vova really wants to play all of them. The initial charge of his laptop battery (i.e. the charge before the start of the game) is k.
The first line of the input contains one integer q (1≤q≤105) — the number of queries. Each query is presented by a single line.
For each query print one integer: -1 if Vova cannot complete the game or the maximum number of turns Vova can just play (make the first type turn) otherwise.
给定四个数字 k, n, a, b, 其中 a > b，要求最大数 i 使得 i a + (n - i) b < n 成立
Training: Regex (Training, Regex)