Cho hai thời điểm: \(a\) giờ \(b\) phút \(c\) giây và \(d\) giờ \(e\) phút \(f\) giây. Hỏi tổng hai thời điểm này bằng bao nhiêu?

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 1000)\) - Thể hiện số testcase.

• \(t\) block tiếp theo, mỗi block chứa \(6\) số nguyên \(a,b,c,d,e,f\), mỗi số trên một dòng ( trong đó: \(0\le a,d\le 1000000\) và \(0\le b,c,e,f\le 59\)).

Output

• Ứng với mỗi testcase, in ra kết quả cần tìm. (Biết rằng kết quả gồm 3 số nguyên \(x,y,z\) được viết cách nhau bởi dấu cách và \(0\le y,z\le 59\)).

Example

3
1 
5 
6 
7 
15 
6
2 
25 
50 
3 
45 
40
10000 
50 
50 
10000 
50 
50 

8 20 12
6 11 30
20001 41 40

An nhìn đồng hồ và thấy đồng hồ có dạng \(hh\text{ : }mm\text{ : }ss\). Hãy chuyển thời gian này ra giây !

Input

• Dòng thứ nhất chứa số \(t\) thể hiện số testcase (\(1\le t\le 100\))

• \(t\) dòng tiếp theo, mỗi dòng chứa xâu \(s\) - Thể hiện thời gian trên đồng hồ

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Example

2
15:07:48
61:25:36

54468
221136

Có một cây tre cao \(n\) mét (\(n\) là số nguyên dương). Ban đầu chú sâu ở gốc của cây tre !

Biết rằng, Cứ \(1\) phút, chú leo lên được \(u\) (mét), và sau đó, chú phải nghỉ ngơi trong \(1\) phút để lấy lại tinh thần, nhưng tiếc thay, trong quá trình nghỉ chú lại bị tụt xuống \(d\) mét.

Hỏi sao bao nhiêu phút, chú sâu leo lên được đỉnh của cây tre. (Ở đây ta hiểu là số phút ít nhất để chú sâu có thể lên được đỉnh cây tre)

Ví dụ: Với \(n=5, u=2, d=1\) thì

• Phút thứ 1: Chú sâu leo lên được \(2m\)
• Phút thứ 2: Chú sâu tụt xuống \(1m\) còn \(1m\)
• Phút thứ 3: Chú sâu leo lên được \(2m\) thành \(3m\)
• Phút thứ 4: Chú sâu tụt xuống \(1m\) còn \(2m\)
• Phút thứ 5: Chú sâu leo lên được \(2m\) thành \(4m\)
• Phút thứ 6: Chú sâu tụt xuống \(1m\) còn \(3m\)
• Phút thứ 7: Chú sâu leo lên được \(2m\) thành \(5m\), đến được đỉnh cây tre

Vậy sau 7 phút chú sâu leo lên được đỉnh cây tre

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase
• \(t\) block tiếp theo, mỗi block gồm \(3\) dòng:
  • Dòng số 1 chứa số nguyên dương \(n\)
  • Dòng số 2 chứa số nguyên dương \(u\)
  • Dòng số 3 chứa số nguyên dương \(d\)

*Biết rằng \(1\le n,u,d\le 1.000.000\) và $d

Một số tự nhiên có \(3\) chữ số được gọi là "tình cảm" nếu chúng có dạng \(\overline{abc}\) trong đó \(a\ne 0\) và \(\overline{abc}=a * a*a+b*b*b+c*c*c\).

Yêu cầu: Cho hai số nguyên dương \(m,n(100\le m\le n\le 900)\). Hãy in ra tất cả các số "tình cảm" có trong đoạn \([m,n]\) theo thứ tự tăng dần mỗi số cách nhau 1 dấu cách (nếu không có số "tình cảm" nào thuộc đoạn \([m,n]\) thì in ra no)

Ví dụ: Với \(m=360; n=380\) thì trong đoạn từ 360 đến 380 có 2 số thỏa mãn:

• Số \(370\) có \(3 \times 3 \times 3 + 7 \times 7 \times 7 +0 \times 0 \times 0 = 27+343+0=370\)
• Số \(371\) có \(3 \times 3 \times 3 + 7 \times 7 \times 7 +1 \times 1 \times 1 = 27+343+1=371\)

nên kết quả in ra 2 số là \(370\ 371\)

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số lượng testcase
• \(t\) block tiếp theo, mỗi block gồm 2 dòng:
  • Dòng số 1 chứa số nguyên dương \(m\)
  • Dòng số 2 chứa số nguyên dương \(n\ (100\le m\le n\le 999)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Example

2
360
380
163
165

370 371
no

An có \(n\) ổ khoá, và ban đầu tất cả ổ khoá này ở trạng thái khoá.

Vì ở nhà quá buồn chán, nên An quyến định đem \(n\) chìa khoá này ra chơi, và quá trình chơi của anh ấy diễn ra như sau:

• Trò chơi, gồm có \(n\) vòng, ở vòng thứ \(i(1\le i\le n)\), anh ấy sẽ đổi trạng thái của tất cả những ổ khoá mà chia hết cho \(i\), tức là ổ nào mở thì anh ấy khoá lại và ngược lại !

Hỏi sau khi kết thúc \(n\) vòng chơi, có bao nhiêu ổ khoá ở trạng thái mở

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa số \(n(1\le n\le 100.000.000)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(66.7\%\) số điểm): \(1\le n\le 100\)
• Subtask \(2\) (\(16.65\%\) số điểm): \(100\le n\le 5000\)
• Subtask \(3\) (\(16.65\%\) số điểm): \(5000\le n\le 100.000.000\)

Example

2
3
5

1
2

Đặt:

\(u_1=1\)

\(u_2=12\)

\(u_3=123\)

\(u_4=1234\)

...

\(u_9=123456789\)

\(u_{10}=1234567891\)

\(u_{11}=12345678912\)

...

\(u_{18}=123456789123456789\)

\(u_{19}=1234567891234567891\)

\(u_{20}=12345678912345678912\)

...

Gọi \(S\) là xâu được tạo ra bằng cách nối liên tiếp các xâu \(u_1,u_2,u_3,...\) (Độ dài của xâu \(S\) là vô tận)

\((S=112123123412345123456...)\)

Ví dụ Với \(n=16\) thì thì số thứ 16 trong \(S\) là số \(1\) nên kết quả ra số \(1\)

Yêu cầu: Cho trước số nguyên dương \(n\). Hãy in ra kí tự thứ \(n\) của xâu \(S\) (biết rằng, xâu \(S\) được đánh chỉ số bằng đầu từ \(1\))

Input

• Một dòng thứ nhất chứa số \(n\ (1\le n\le 10^9)\)

Output

• In ra đáp án cần tìm

Example

10

4

Scoring

• \(60\%\) : \(1\le n\le 1000000\)
• \(40\%\) : Không có điều kiện gì