Eulampius has created a game with the following rules: there are two players in the game: a human and a computer; the game lasts for no more than (n) rounds. Initially both players have (0) points. In the (j)-th round the human gains (a_j) points, and the computer gains (b_j) points. The points are gained simultaneously; the game ends when one of the players gets (k) or more points. This player loses the game. If both players get (k) or more points simultaneously, both lose; if both players have less than (k) points after (n) rounds, the game ends in a tie; after each round the human can push the "Reset" button. If the human had (x) points, and the computer had (y) points before the button is pushed (of course, (x < k) and (y < k)), then after the button is pushed the human will have (x' = max(0, \, x - y)) points, and the computer will have (y' = max(0, \, y - x)) points. E. g. the push of "Reset" button transforms the state ((x=3, \, y=5)) into the state ((x'=0, \, y'=2)), and the state ((x=8, \, y=2)) into the state ((x'=6, \, y'=0)). Eulampius asked his friend Polycarpus to test the game. Polycarpus has quickly revealed that amounts of points gained by the human and the computer in each of (n) rounds are generated before the game and stored in a file. In other words, the pushes of the "Reset" button do not influence the values (a_j) and (b_j), so sequences (a) and (b) are fixed and known in advance. Polycarpus wants to make a plan for the game. He would like to win the game pushing the "Reset" button as few times as possible. Your task is to determine this minimal number of pushes or determine that Polycarpus cannot win. The first line of the input contains one integer (t) ((1 \le t \le 10000)) — the number of test cases. Then the test cases follow. The first line of each test case contains two integers (n) and (k) ($$$1 \le n \le 2 \cdot 10^