Trong một vũ trụ song song, Prototype chuẩn bị nói lời chia tay với hai người bạn thân là uou và nhatnam3004.
Để thử thách tình bạn trước khi rời đi, Prototype đưa ra một bài toán cổ xưa về những con số may mắn.

Nếu hai người bạn giải được, lời chia tay sẽ trở thành một lời hứa gặp lại.

Bài toán

Cho 4 số nguyên dương \(a, b, c, d\).

Gọi \(S\) là tổng của chúng:

Gọi \(S_{rev}\) là số đảo ngược của \(S\)
(ví dụ: \(S = 123 \Rightarrow S_{rev} = 321\)).

Trường hợp 1:

Nếu cả \(S\) và \(S_{rev}\) đều là số nguyên tố, khi đó:

Trường hợp 2:

Nếu ít nhất một trong hai không phải số nguyên tố, khi đó:

Trong đó:

• Phép chia \(\frac{a}{b}\) được hiểu là:

• \(b^{-1}\) là nghịch đảo modulo của \(b\) theo modulo \(M = 10^9 + 7\)

Lưu ý

• Nếu trong Trường hợp 2, \(b\) chia hết cho \(10^9 + 7\)
  ⇒ không tồn tại nghịch đảo modulo, in ra: \(-1\)
• Ta nhận thấy bốn số a b c d khi cộng lại sẽ có giá trị lên đến \(4* 10 ^ {18}\) và khi đảo số sẽ có thể khiến số vượt giá trị mà long long cho phép, đối với trường hợp này chúng ta sẽ kiểm tra nguyên tố luôn bằng số bị tràn đó. Nếu bạn dùng python, để AC bạn sẽ phải mô phỏng lại sự tràn số đó của long long. Để mô phỏng được điều đó các bạn có thể sử dụng đoạn code sau đây
  
  Python

  def ll(n):
  n = n % (2**64)
  if n >= 2**63:
  n -= 2**64
  return n
  

Input

• Dòng đầu chứa số nguyên \(Q\) \((1 \le Q \le 10^5)\) — số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng gồm 4 số:

Output

• Với mỗi truy vấn, in ra một số nguyên \(Res\) trên một dòng.

Example

1
205 435 329 325

939494804

Scoring

• Subtask 1 (\(20\%\) điểm): \(Q \le 100\), \(a, b, c, d \le 10^3\).
• Subtask 2 (\(20\%\) điểm): \(Q \le 10^3\), \(a, b, c, d \le 10^6\).
• Subtask 3 (\(20\%\) điểm): \(Q \le 10^4\), \(a, b, c, d \le 10^9\).
• Subtask 4 (\(40\%\) điểm): \(Q \le 10^5\), \(a, b, c, d \le 10^{18}\).