Skr has decided to hide all the cryptocurrency he had been mining for years, using a modified Blueberry PIE device that he secretly installed in his friend’s house. To properly do this, he obtained a map, drew an X mark on it, then he went to the spot that’s at the exact intersection of the lines that form the letter X, and buried his cryptowallet there. He also put a password on his cryptowallet so that nobody else could spend his money, even if the wallet was coincidentally found.

Being the cautious type, Skr actually divided his entire cryptosavings into \(\mathbf{T}\) different cryptowallets and followed the same cryptoprocedure described above for each of those cryptowallets, using \(\mathbf{T}\) different maps in total. Unfortunately, though, due to his busy work schedule as a lifeguard at the swimming pool at the Olympics, he completely forgot where he placed all those maps. (Karma?) He still remembers the coordinates of the points that constitute the 4 corners of each X mark he drew, but he couldn’t remember exactly where he buried any of his cryptowallets. Moreover, the locations of the cryptowallets aren’t the only thing Skr needs your help with. He apparently needs your programming skills to also remember the password of each of his wallets. The passwords of all of Skr’s cryptowallets are related to the following equation.

\(\mathbf{X_{wallet} \cdot x + Y_{wallet} \cdot y = M}\)

The values \(\mathbf{X_{wallet}}\) and \(\mathbf{Y_{wallet}}\) indicate the coordinates where a particular cryptowallet is buried while \(\mathbf{M}\) denotes the amount of cryptocurrency in that cryptowallet. The password for that particular cryptowallet is the number of positive integer pairs \(\mathbf{(x, y)}\) that satisfy the equation above.

Let’s see if you can crack the password of all of Skr’s cryptowallets.

Input

The first line of input has a single positive integer \(\mathbf{T}\), indicating the number of cryptowallets Skr buried.

Each of the following \(\mathbf{T}\) lines has 9 integers in the following order: \(\mathbf{A_x}\), \(\mathbf{A_y}\), \(\mathbf{B_x}\), \(\mathbf{B_y}\), \(\mathbf{C_x}\), \(\mathbf{C_y}\), \(\mathbf{D_x}\), \(\mathbf{D_y}\), and \(\mathbf{M}\). The integer pairs \(\mathbf{(A_x, A_y)}\), \(\mathbf{(B_x, B_y)}\), \(\mathbf{(C_x, C_y)}\), and \(\mathbf{(D_x, D_y)}\) denote the coordinates of the points \(\mathbf{A, B, C}\) and \(\mathbf{D}\) respectively. One of the lines forming the X mark Skr drew is between points \(\mathbf{A}\) and \(\mathbf{B}\), while the other one is between points \(\mathbf{C}\) and \(\mathbf{D}\). Finally, the integer \(\mathbf{M}\) indicates the amount of cryptocurrency stored in that particular wallet.

• \(0 < \mathbf{A_x, A_y, B_x, B_y, C_x, C_y, D_x, D_y} \leq 10^4\)
• \(0 < \mathbf{M} \leq 10^9\)
• \(0 < \mathbf{T} \leq 10^4\)

Output

Your code should produce an output with \(\mathbf{T}\) lines, where \(\mathbf{T}\) is the same value stored in the first line of the relevant input. \(i^{th}\) line of the input should have a single integer, which should be the password of the cryptowallet clues given in the \((i+1)^{th}\) line of the input.

Note: You may assume that the lines forming each X mark intersect at point coordinates, which are integers.

Example

Input 1:

1
5 5 1 3 3 2 3 6 7

Output 1:

1

Input 2:

1
2 6 4 4 2 4 4 6 70

Output 2:

4