NAJPF  Pattern Find
Your task is so simple given a string and a pattern. You find the pattern on the given string. If found print how many time found the pattern and their index. Otherwise print ‘Not Found’
Input:
The input line consists of a number T (1 ≤ T ≤ 50) test cases.
For each case given two string number A,B. the string and the pattern 1 ≤A, B ≤10^6
All character will be lower case Latin character. And   is the length of string.
Output:
For each case print the number (found pattern from the given string) next line there position And Otherwise print 'Not Found' without quota.
There will a blank line between two cases.
Sample:
Input 
Output 
3 
3 
Hints:
hide comments
medhruv7:
20200501 14:30:01
rabin karp AC one go :) 

riyansh16_:
20200414 21:11:43
can be done by brute force with a time complexity of O(n)


alphatheta:
20200405 23:48:27
AC with Polynomial Hashing: 0.24s 

pandey101299:
20191202 18:02:13
with Z algo in 0.19 secs


pumpkinduke:
20191114 18:27:48
Guys beware of giving the space between numbers.it cost me many WA ___ 

fardin_abir:
20191031 08:09:37
ac with kmp in .16 s 

tpriyanshu:
20191015 03:02:07
If you are doing rabinkarp, and getting TLE, make sure you take care of the case when hash becomes ve. Simply add mod to it. 

magetron:
20190908 14:32:08
test case is rather weak, submiited a wrong solution and got accepted


mostafa_haamed:
20190821 21:43:00
ac from first hit using z algorithm 

copperium:
20190812 05:39:32
"Not Found" has both words capitalized, cost me 2 WA 
Added by:  Najmuzzaman 
Date:  20141023 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 