Để chuẩn bị cho kỳ thi Olympic, nhóm bạn NaTaLo đã luyện rất nhiều về công thức tính tổng các ước của một số nguyên dương, đến nỗi trong giấc mơ, bạn gặp một ác mộng như sau: Ban tổ chức cho các bạn một con số nguyên dương, chính là điểm kinh nghiệm của các bạn ấy hiện tại (tính theo đơn vị EXP). Các bạn cần tính tổng các ước số dương của số đó để được số mới (chú ý rằng nếu ~a~ chia hết cho ~b~ thì ~b~ là một ước của ~a~), có thể xem là kỹ năng của các bạn ấy tích lũy được sau mỗi năm là bao nhiêu. Cứ làm như thế nhiều lần cho đến khi nào đạt được level đủ để tham gia Siêu cúp, tức là một ngàn tỷ EXP, thì mới thôi! Các bạn tính xong và giật mình với số năm đó, hãy cùng các bạn ấy trải nghiệm nỗi sợ đó nhé.

Input

Một dòng là số nguyên dương ~n~ với ~1 \le n \le 10^{12}~ cho biết điểm kinh nghiệm của nhóm bạn hiện tại.

Output

Một số nguyên duy nhất là đáp số của bài toán (cho biết rằng giá trị này vẫn tính được trong kiểu Int64). Nếu không thực hiện được thì in ra ~-1.~

Sample input 1

999999999999

Sample output 1

1

Sample input 2

2

Sample output 2

28

Trong Ví dụ 1, các bạn ấy chỉ cần tốn một năm là đạt được; còn trong Ví dụ 2, các bạn ấy còn phải luyện thêm gần ~30~ năm: ~2 \to 3 \to 4 \to 7 \to 8 \to 15 \to ...~ giấc mơ Siêu cúp còn hơi xa xôi.

Vào ngày thi cuối kỳ Nhập môn lập trình, thầy Tina phát cho lớp DHCNTT gồm ~n~ sinh viên một danh sách ~2n~ số nguyên, không nhất thiết phân biệt. Lớp trưởng Đức Nam có nhiệm vụ phân chia các số đó cho các bạn, mỗi người nhận về hai số. Nhiệm vụ của các sinh viên là in ra hệ số ~a,b~ của phương trình bậc hai ~x^2+ax+b=0~ nhận hai số mình đang giữ là nghiệm. Chẳng hạn nếu sinh viên nhận được hai số ~-3,4~ thì sẽ trả ra ~a=-1,b=-12.~

Lớp trưởng của lớp muốn kết quả thú vị hơn nên cố gắng phân chia sao cho số lượng số lẻ mà các bạn mình in ra được là nhiều nhất. Hãy giúp Nam tìm ra số lượng đó trước khi thầy Tina tính giờ làm bài nhé, Nam chỉ có ~2~ giây thôi.

Input

Dòng đầu tiên là số nguyên dương ~n \le 10^5.~ Dòng tiếp theo gồm ~2n~ số nguyên, không nhất thiết phân biệt.

Output

In ra đáp số của bài toán.

Sample input 1

2

1 2 3 4

Sample output 1

2

Sample input 2

1

0 -4

Sample output 2

0

Trong Ví dụ 1, ta thấy có các cách chia: ~(1,2),(3,4)~, hoặc ~(1,3),(2,4)~ hoặc ~(1,4),(2,3)~.

• Ứng với cách chia ~(1,2),(3,4)~, các hệ số ~(a,b)~ lần lượt là ~-3,2~ và ~-7,12~ nên số lượng số lẻ là 2.

• Ứng với cách chia ~(1,3),(2,4)~, các hệ số ~a,b)~ lần lượt là ~-4,3~ và ~-6,8~ nên số lượng số lẻ là 1.

• Ứng với cách chia ~(1,4),(2,3)~, các hệ số ~(a,b)~ lần lượt là ~-5,4~ và ~-5,6~ nên số lượng số lẻ là 2.

Do đó, đáp số cần tìm là ~2~. Còn trong Ví dụ 2, cặp số nhận được luôn cho kết quả ~a=4,b=0~ nên số lượng số lẻ là ~0~.

Do phải chấm quá nhiều bài kiểm tra của sinh viên IUH nên mắt của thầy Luna đã dần yếu kém, dù thầy thường xuyên sử dụng thuốc nhỏ mắt Osla. Một ngày nọ, trong lúc ký một số giấy tờ, trong đó có các con số nguyên dương rất lớn, thầy đọc nhầm từ chữ số ~x~ sang chữ số ~y~ và sai lầm này là diễn ra hàng loạt. Chẳng hạn đang có số ~151~, mà thầy đọc nhầm chữ số ~1 \to 7~ thì số mới sẽ thành ~757~. Việc sai sót này có thể ít nhiều gây ra các hậu quả, trước mắt là chênh lệch giá trị của số cũ và số mới. Bạn hãy giúp thầy Luna tính toán ra hậu quả đó trên một số tự nhiên ~n~ nhé.

Input

Một dòng duy nhất gồm ba số nguyên ~n,x,y~, trong đó ~0 \le n \le 10^{12}~ và ~0 \le x, y \le 9~, đồng thời ~x \neq y.~

Output

Một dòng duy nhất là đáp số của bài toán.

Sample input 1

151 1 7

Sample output 1

606

Sample input 2

2022 4 5

Sample output 2

0

Ở Ví dụ 1, ta thấy từ số ~151~, thầy Luna lại nhầm sang ~757~ nên chênh lệch là ~757-151=606~. Còn trong Ví dụ 2, may mắn là sự nhầm lẫn từ ~4~ sang ~5~ lại không ảnh hưởng đến con số ~2022~.

Vào một buổi sáng đầu hè đẹp trời, Tèo rũ Tí lại chơi Hyperrectangle" (Siêu chữ nhật) - Đó là một trò chơi đối kháng, chiến thuật, mang cả yếu tố giải đố và vô cùng trí tuệ.

"Hyperrectangle" sẽ bắt đầu bằng việc chơi trên một khối {siêu hộp chữ nhật) (Hyperrectangle) - là một khối ~n~ chiều được tạo bởi các khối siêu lập phương (hypercube), các mặt của nó là một hình chữ nhật mà ở chiều thứ ~i~ chứa ~a_i~ khối siêu lập phương. Trong khối siêu chữ nhật đó có chứa một khối siêu lập phương đặc biệt ở vị trí {~x_1, x_2, ..., x_n~}, khối siêu lập phương đó là một siêu vật chất vô cùng giá trị mà ai cũng muốn có được. Và mục tiêu của trò chơi cũng là đạt được siêu vật chất đó.

Để 2 người chơi có thể khai thác khối siêu chữ nhật thì mỗi người sẽ sử dụng một siêu công cụ để tương tác. Siêu công cụ này là một thiết bị có thể khai thác một siêu mặt phẳng mà chỉ chứa các khối siêu lập phương bên ngoài. Mỗi lượt mỗi người chơi sẽ luân phiên phải sử dụng siêu công cụ một lần để khai thác các khối siêu lập phương. Ai bằng việc sử dụng siêu công cụ để đạt được siêu vật chất rước sẽ dành chiến thắng.

Trong đó: Siêu lập phương bên trong là khối siêu lập phương bị tiếp xúc (bao phủ) ở tất cả các $n$ chiều bề mặt của khối. Và siêu lập phương bên ngoài là những siêu khối không phải siêu lập phương bên trong.

Biết rằng 2 bạn Tèo và Tí đã là những cao thủ của trò chơi này. Nên cả 2 sẽ luôn thực hiện những bước đi tối ưu nhất mà họ có thể làm được. Và vì Tèo là người rũ nên Tí sẽ là người đi trước

Với vai trò là những người ở sau bức tường thứ tư (Fourth wall), tôi muốn hỏi bạn rằng nếu bạn hiểu đề bài trên, thì hãy tìm ra người chiến thắng cho trò chơi này.

InputFile

Dòng đầu tiên chứa một số nguyên dương ~t~ - Số lượng testcase

~T~ bộ dòng tiếp theo mỗi dòng gồm ~3~ dòng:

• Dòng đầu tiên chứa một số nguyên dương ~n~ - Số chiều của không gian của khối siêu hộp chữ nhật (~ n \leq 10^{6}~)

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ - Độ dài của khối siêu hộp chữ nhật ở chiều thứ ~i~. (~a_i \leq 10^{18}~)

• Dòng thứ ba chứa ~n~ số nguyên dương ~x_i~ - Tọa độ ở chiều thứ $i$ của khối siêu lập phương có chứa siêu vật chất .(~ 1 \leq x_i \leq a_i~)

• Biết: Tọa độ ở mỗi chiều thứ $i$ sẽ bắt đầu là $1$ và kết thúc là ~a_i~.

Luôn đảm bảo tổng số ~n~ của tất cả testcase luôn ~\leq 10^{6}~

OutputFile

Một dòng duy nhất chứa một trong hai chuỗi "Teo" hoặc "Ti" - đại diện cho việc ai sẽ chiến thắng trò chơi "Hyperrectangle" ở trên nếu bạn hiểu đề.

Sample Input

2
1
3
2
1
1
1

Sample Output

Teo
Ti

Cách tính điểm

• Subtest 1: (~50\%~ số điểm) Với ~n \leq 1~ & ~a_i, x_i \leq 10^1~
• Subtest 2: (~20\%~ số điểm) Với ~n \leq 2~ & ~a_i, x_i \leq 10^2~
• Subtest 3: (~10\%~ số điểm) Với ~n \leq 3~ & ~a_i, x_i \leq 10^3~
• Subtest 4: (~20\%~ số điểm) Với ~n \leq 10^{6}~ & ~a_i, x_i \leq 10^{18}~

Vào một ngày hè rãnh rỗi Tèo nghĩ ra một trò chơi thú vị, tư duy và không kém phần sáng tạo. Cậu ta lấy một sợi dây có độ dài là ~k~ cm (Với đầu mút bên trái là vị trí ~0~ và đầu mút bên phải là vị trí ~k~) và bôi một lớp mật ong lên sợi dây và căng ra hai đầu.

Sau đó, Tèo chợp mắt một lát trong lúc chờ đợi lũ kiến bị dụ đến. Lúc tỉnh dậy, Tèo đã thấy kiến bu đầy trên sợi dây. Một số con đang đi về đầu mút bên phải của sợi dây trong khi số còn lại thì đang đi về đầu mút bên trái. Vì sợi dây khá mảnh nên hai con kiến sẽ không thể đi qua nhau. Vì vậy chúng có một quy luật khá đặc biệt là: Nếu hai con kiến đụng đầu nhau, chúng sẽ lập tức đổi hướng đi. Tèo đã đánh số các con kiến trên dây từ ~1~ đến ~n~ và ghi lại vị trí cũng như hướng di chuyển của nó tương ứng ~a_i~ (với ~|a_i|~ là vị trí của con kiến và nếu ~a_i<0~ thì con kiến đang đi sang phải còn ~a_i>0~ thì con kiến đang đi sang trái). Nếu một con kiến đi tới một trong hai đầu mút của sợi dây thì ngay lúc đó nó coi như đã rời khỏi sợi dây.

Tèo muốn đố bạn rằng tổng thời gian để con kiến cuối cùng rời khỏi sợi dây là giây thứ mấy? Biết rằng các con kiến di chuyển với vận tốc ~1~cm/s.

Ví dụ: Sợi dây dài ~k = 4~ và ~3~ con kiến ở vị trí ~1~, ~2~, ~3~ và đi về hướng đầu mút lần lượt là phải, trái, trái.

Tại giây ~0.5~, con kiến ~1~ chạm con kiến ~2~ tại vị trí ~1.5~ và chúng đổi chiều.

Tại giây ~1~, con kiến ~2~ chạm con kiến ~3~ tại vị trí ~2~ và chúng đổi chiều.

Tại giây ~2~, con kiến ~1~ chạm đến vị trí đầu mút trái. Đồng nghĩa với việc con kiến ~1~ rời khỏi sợi dây.

Tại giây ~3~, con kiến ~2~ chạm đến vị trí đầu mút trái và con kiến số ~3~ chạm vị trí đầu mút phải. Đồng nghĩa với việc con kiến ~2~ và con kiến ~3~ rời khỏi sợi dây.

Vậy thời điểm con kiến cuối cùng rời khỏi sợi dây là giây thứ ~3~.

InputFile

Dòng đầu tiên chứa một số nguyên dương ~t~ - Số lượng testcase

~T~ bộ dòng tiếp theo mỗi dòng gồm ~2~ dòng:

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ lần lượt là số con kiến và độ dài của sợi dây ~(~Với ~0 < n < k)~.

• Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ là vị trí và hướng của những con kiến đó. Với ~|a_i|~ là vị trí của nó trên sợi dây và nếu ~a_i~ là âm thì nó đang đi về đầu mút bên phải hoặc ~a_i~ là dương thì nó đang đi về đầu mút bên trái ~(~Với ~0 < |a_i| < k~, ~1 \le i \le n)~. Luôn đảm bảo ~0 < |a_1| < |a_2| < ... < |a_n| < k~.

Luôn đảm bảo tổng số ~n~ của tất cả testcase luôn ~\leq 10^{6}~

OutputFile

Một dòng duy nhất là một số nguyên dương đại diện cho thời điểm con kiến cuối cùng rời khỏi dây.

Sample Input

1 
3 4
-1 2 3

Sample Outpt

3

Cách tính điểm:

• Subtest 1: (~50\%~ số điểm) Với ~n \le 10^2~ và ~k \le 10^3~.
• Subtest 2: (~30\%~ số điểm) Với ~n \le 10^3~ và ~k \le 10^6~.
• Subtest 3: (~20\%~ số điểm) Với ~n \le 10^6~ và ~k \le 10^{18}~.